5,323
edits
Parallel Algorithms: Difference between revisions
→A second connectivity algorithm
| Line 530: | Line 530: | ||
Each iteration takes constant time. | Each iteration takes constant time. | ||
# Probe quitting: each rooted star whose supervertex is not adjacent to any other quits | |||
# Hooking on smaller: each rooted star hooks onto a smaller vertex of another supervertex which is not a leaf | |||
* Hooking non-hooked-upon: | #* Note that this is not unique. Requires arbitrary CRCW. | ||
# Hooking non-hooked-upon: every rooted star not hooked upon in step 2 hooks to another vertex in another supervertex which is not a leaf | |||
# Parallel pointer jumping: one round of parallel pointer jumping | |||
===Minimum Spanning Forest=== | ===Minimum Spanning Forest=== | ||