5,323
edits
Parallel Algorithms: Difference between revisions
→Minimum Spanning Forest
No edit summary Tag: visualeditor |
|||
| Line 635: | Line 635: | ||
===Minimum Spanning Forest=== | ===Minimum Spanning Forest=== | ||
minimum | ====The MSF Theorem==== | ||
Let <math>G(V,E)</math> be a weighted graph and let <math>U</math> and <math>V-U</math> be two non-empty subsets of <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> | |||
==Hardware/Architecture== | ==Hardware/Architecture== | ||
[http://users.umiacs.umd.edu/~vishkin/XMT/vCarageaLeebook.pdf Models for Advancing PRAM and Other Algorithms into Parallel Algorithms for PRAM] | [http://users.umiacs.umd.edu/~vishkin/XMT/vCarageaLeebook.pdf Models for Advancing PRAM and Other Algorithms into Parallel Algorithms for PRAM] | ||