5,323
edits
Parallel Algorithms: Difference between revisions
→A first MSF algorithm
Tag: visualeditor-switched |
|||
| Line 645: | Line 645: | ||
Each round consists of hooking and <math>\log n</math> rounds of parallel pointer jumping | Each round consists of hooking and <math>\log n</math> rounds of parallel pointer jumping | ||
* Each root find the minimum weight edge to another supervertex and hooks itself to that root. | * Each root find the minimum weight edge to another supervertex and hooks itself to that root. | ||
*: This is automatic from the priority CRCW. | |||
====A second MSF algorithm==== | |||
We replace steps 2 and 3 in the connectivity algorithm with the simple rule: | |||
* We hook rooted stars using the edge with the smallest weight. | |||
;Notes | |||
* The progression of edge weights up the tree are monotonically increasing so there are no cycles | |||
==Hardware/Architecture== | ==Hardware/Architecture== | ||