5,337
edits
Parallel Algorithms: Difference between revisions
→List Ranking Cluster
| Line 328: | Line 328: | ||
==List Ranking Cluster== | ==List Ranking Cluster== | ||
Techniques: Euler tours, pointer jumping, randomized and deterministic symmetry breaking | Techniques: Euler tours, pointer jumping, randomized and deterministic symmetry breaking | ||
===Rooting a tree=== | |||
Inputs | |||
* Vector of vertices which point to an index in edges | |||
* Vector of edges e.g. (1,2) | |||
* Vector of pointers to identical edges e.g. index of (1,2) -> index of (2,1) | |||
Algorithm | |||
* Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math> | |||
==Resources== | ==Resources== | ||