Expected linear time MST algorithm
The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.
- Comment
- enThe expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.
- Depiction
- Has abstract
- enThe expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected 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.
- Is primary topic of
- Expected linear time MST algorithm
- Label
- enExpected linear time MST algorithm
- Link from a Wikipage to an external page
- www.cs.technion.ac.il/~idddo/mstverif.pdf
- Link from a Wikipage to another Wikipage
- Binary tree
- Borůvka's algorithm
- Category:Randomized algorithms
- Category:Spanning tree
- David Karger
- Divide and conquer algorithms
- Expected value
- File:Boruvka Step 1.svg
- File:Boruvka Step 2.svg
- File:Boruvka Step 3.svg
- File:Boruvka Step 4.svg
- File:Boruvka Step 5.svg
- File:Linear MST Algorithm Left Subchildren.svg
- Geometric series
- Glossary of graph theory
- Graph (discrete mathematics)
- Greedy algorithms
- Isolated vertex
- Kruskal's algorithm
- Linearity of expectation
- Linear time
- Minimum spanning forest
- Minimum spanning tree
- Negative binomial distribution
- Prim's algorithm
- Randomized algorithm
- Randomized algorithms
- Recursion (computer science)
- Reverse-delete algorithm
- Robert Tarjan
- Weighted graph
- SameAs
- 4k3j1
- Expected linear time MST algorithm
- m.0j9ngld
- Q5420845
- الگوریتم میانگین–خطی درخت پوشای کمینه
- Subject
- Category:Randomized algorithms
- Category:Spanning tree
- Thumbnail
- WasDerivedFrom
- Expected linear time MST algorithm?oldid=1051508644&ns=0
- WikiPageLength
- 14376
- Wikipage page ID
- 35516383
- Wikipage revision ID
- 1051508644
- WikiPageUsesTemplate
- Template:Reflist
