5,323
edits
Parallel Algorithms: Difference between revisions
→A second connectivity algorithm
| Line 540: | Line 540: | ||
* The pointer graph always consists of rooted trees. | * The pointer graph always consists of rooted trees. | ||
* For every vertex which is not a leaf, <math>D(v) \leq v</math> | * For every vertex which is not a leaf, <math>D(v) \leq v</math> | ||
*: {{hidden | Proof | | |||
* This is true after steps 1, 2, and 4. | |||
** This follows immediately for 1 and 2. | |||
** After one round of pointer jumping (4) after 3, everyone from supervertex <math>r</math> is a leaf due to the claim below. | |||
* Consider a root <math>r</math> which hooks on someone larger in step 3. | |||
*: After Step 3, all children of <math>r</math> are leaves. | |||
*: I.e. no one else will hook to <math>r</math> during Step 3. | |||
** If anyone was larger, <math>r</math> would have hooked on them in Step 2. | |||
** If anyone was smaller, they would have hooked on <math>r</math> in Step 2. | |||
}} | |||
;Complexity | ;Complexity | ||
* Time <math>O(\log n)</math> | * Time <math>O(\log n)</math> | ||
* Work <math>O((n+m)\log n)</math> | * Work <math>O((n+m)\log n)</math> | ||
;Notes | |||
* In step 2, you can also hook rooted trees for better empirical performance | |||
{{ hidden | Proof | | {{ hidden | Proof | | ||