1
$\begingroup$

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?

$\endgroup$

0

Your Answer

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