5,323
edits
Parallel Algorithms: Difference between revisions
→Minimum Spanning Forest
Tag: visualeditor-switched |
|||
| Line 639: | Line 639: | ||
Consider set <math>H=\{(u,v) \mid u \in U, v \in V\}</math> of edges connecting points in <math>U</math> and <math>V</math>. | Consider set <math>H=\{(u,v) \mid u \in U, v \in V\}</math> of edges connecting points in <math>U</math> and <math>V</math>. | ||
If <math>e</math> is the edge of minimum weight in <math>H</math>, then <math>e</math> is in the MSF of <math>G</math> | If <math>e</math> is the edge of minimum weight in <math>H</math>, then <math>e</math> is in the MSF of <math>G</math> | ||
====A first MSF algorithm==== | |||
* Sort the edges by weight. Assign a processor to each edge. Using a priority CRCW, the edge with minimum weight will take priority during writes. | |||
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. | |||
==Hardware/Architecture== | ==Hardware/Architecture== | ||