I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia:

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. (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 \neq u$, i.e. starts from a different node, set $first(u)=(u,v)$

    • Else if $x \neq 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:

$ \mathrm{succ}(u,v)=\begin{cases} \mathrm{next}(v,u) & \mathrm{next}(v,u)\neq \mathrm{nil} \\ \mathrm{first}(v)&\text{otherwise}. \end{cases}$

Why the edge list constructed in the last step is an Euler tour? What theorem or lemma gurantees that every single edge is visited?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.