5,323
edits
Parallel Algorithms: Difference between revisions
→A first connectivity algorithm
| Line 510: | Line 510: | ||
The first connectivity algorithm consists of <math>\log(n)</math> iterations of the following two steps: | The first connectivity algorithm consists of <math>\log(n)</math> iterations of the following two steps: | ||
* Hookings - Each root hooks itself the the minimal adjacent root | * Hookings - Each root hooks itself the the minimal adjacent root. If there are no adjacent stars, then this rooted star quits. | ||
* Parallel pointer jumping - Each vertex performs pointer jumping until every vertex points to the root, forming a rooted star. | * Parallel pointer jumping - Each vertex performs pointer jumping until every vertex points to the root, forming a rooted star. | ||
;Theorems | |||
# The pointer graph always consists of rooted trees. | |||
# After <math>\log n</math> iterations, all vertices are contained in rooted stars that quit. | |||
#: Each connected component is represented by a single rooted star. | |||
;Complexity | ;Complexity | ||