5,323
edits
Parallel Algorithms: Difference between revisions
→Rooting a tree
(→Tricks) |
|||
| Line 400: | Line 400: | ||
**Now we have an euler cycle (or euler tour) among the edges | **Now we have an euler cycle (or euler tour) among the edges | ||
*Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math> | *Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math> | ||
** The edge <math>u_{r,1} \rightarrow r</math> is the opposite edge of the first edge coming out of <math>r</math> | |||
*Step 4: Apply a list ranking algorithm to the edges. | *Step 4: Apply a list ranking algorithm to the edges. | ||
*Step 5: Delete the edge between every two vertices with the lower ranking | *Step 5: Delete the edge between every two vertices with the lower ranking | ||