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 is true after steps 1, 2, and 4. | ||
** This follows immediately for 1 and 2. | ** This follows immediately for 1 and 2. | ||