The Euler tour technique (ETT), named after Leonhard Euler

Leonhard Euler

Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...

, is a method in graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

 for representing trees

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

. The tree is viewed as a directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 that contains two directed edges for each edge in the tree. The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation (ETR) of the tree. The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory. It was introduced by Tarjan and Vishkin in 1984.

Construction

Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows:

• We construct a symmetric list of directed edges:
  • For each undirected edge {u,v} in the tree, insert (u,v) and (v,u) in the edge list.
• Sort the edge list lexicographically
  Lexicographical order
  In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
  
  . (Here we assume that the nodes of the tree are ordered, and that the root is the first element in this order.)
• Construct adjacency lists for each node (called next) and a map from nodes to the first entries of the adjacency lists (called first):
  • For each edge (u,v) in the list, do in parallel:
    • If the previous edge (x,y) has x ≠ u, i.e. starts from a different node, set first(u) = (u,v)
    • Else if x = u, i.e. starts from the same node, set next(x,y) = (u,v)

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.

Roots, advance and retreat edges

If the tree has a root, we can split the circular list succ at that root. In that case, we can speak of advance and retreat edges: given a pair of nodes u,v, the first occurrence of either (u,v) or (v,u) in the ETR is called the advance edge, and the second occurrence is called the retreat edge. This appeals to the intuition that the first time such an edge is traversed the distance to the root is increased, while the second time the distance decreases.

Applications

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

Prefix sum

In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....

 problem in parallel for a list of n items):

1. Classifying advance and retreat edges: Do list ranking on the ETR and save the result in a two-dimensional array A. Then (u,v) is an advance edge iff A(u,v) < A(v,u), and a retreat edge otherwise.
2. Determine the level of each node: Do a prefix sum on the ETR, where every advance edge counts as 1, and every retreat edge counts as −1. Then the value at the advance edge (u,v) is the level of v.
3. Number of nodes in a subtree rooted at v: determine advance edge (u,v), and the retreat edge (u,v) in parallel, and then count the number of advance edges between (u,v) and (u,v) using prefix sum.
4. The depth-first search
   Depth-first search
   Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
   
   index of a node v: count the number of advance edges up to and including (u,v).

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.