Content deleted Content added
Kyle.cackett (talk | contribs) No edit summary |
Kyle.cackett (talk | contribs) No edit summary |
||
Line 1:
A [[randomized algorithm]] for computing the [[minimum spanning forest]] of a [[weighted graph]] with no [[isolated vertex|isolated vertices]]. It was developed by [[David Karger]], Philip Klein, and [[Robert Tarjan]]
<ref>{{citation
| last1 = Karger | first1 = David R. | author1-link = David Karger
| last2 = Klein | first2 = Philip N.
| last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan
| doi = 10.1145/201019.201022
| mr = 1409738
| issue = 2
| journal = [[Journal of the Association for Computing Machinery]]
| pages = 321–328
| title = A randomized linear-time algorithm to find minimum spanning trees
| volume = 42
| year = 1995}}</ref>. The algorithm relies on techniques from [[Borůvka's algorithm]] along with an algorithm for [[MST verification algorithm|verifying a minimum spanning tree in [[linear time]]
<ref name=MST-V1>{{cite journal
| last1 = Dixon | first1 = Brandon
| last2 = Rauch | first2 = Monika
| last3 = Tarjan | first3 = Robert
| author3-link = Robert Tarjan
| title = Verification and sensitivity analysis of minimum spanning trees in linear time
| journal = SIAM J. on Computing
| volume = 21
| pages = 1184–1192
| year = 1992
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.25
}}</ref>
<ref name=MST-V2>
{{cite conference
| last1 = King | first1 = Valerie
| title = A Simpler Minimum Spanning Tree Verification Algorithm
| booktitle = Proceedings of the 4th International Workshop on Algorithms and Data Structures
| year = 1995
| pages = 440-448
| url = http://dl.acm.org/citation.cfm?id=645930.672859
| publisher = Springer-Verlag
| ___location = London, UK, UK
}}
</ref>. It combines the design paradigms of [[divide and conquer algorithms]], [[greedy algorithms]], and [[randomized algorithms]] to achieve [[Expected value|expected]] [[linear time|linear performance]].
Deterministic algorithms that find the minimum spanning tree include [[Prim's algorithm]], [[Kruskal's algorithm]], [[Reverse-Delete algorithm]], and [[Borůvka's algorithm]].
==Overview==
The key insight to the algorithm is a random sampling step which partitions a graph into two [[Glossary_of_graph_theory#Subgraphs|subgraphs]] by randomly selecting edges to include in each subgraph. The algorithm recursively finds the [[minimum spanning tree|minimum spanning forest]] of the first subproblem and uses the solution in conjunction with the [[MST verification algorithm|linear time verification algorithm]] to discard edges in the graph that cannot be in the minimum spanning tree. A procedure taken from [[Borůvka's algorithm]] is also used to reduce the size of the graph at each [[Recursion (computer science)|recursion]].
| |||