Euler tour technique

The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory.

[1] Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows: Construct an edge list (called succ) in Euler tour order by setting pointers succ(u,v) for all edges (u,v) in parallel according to the following rule: The resulting list succ will be circular.

The overall construction takes work W(n) = O(sort(n)) (the time it takes to sort n items in parallel) if the tree has n nodes, as in trees the number of edges is one less than the number of nodes.

Rerooting the tree can be done in constant time O(1) by splitting the circular list succ at the new root.

All of the following problems can be solved in O(Prefix sum(n)) (the time it takes to solve the prefix sum problem in parallel for a list of n items): Henzinger and King[2] suggest to represent a given tree by keeping its Euler tour in a balanced binary search tree, keyed by the index in the tour.