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.[1] The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time.[2][3] 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.
- ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022. S2CID 832583.
- ^ Dixon, Brandon; Rauch, Monika; Tarjan, Robert E. (1992). "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time". SIAM Journal on Computing. 21 (6): 1184. CiteSeerX 10.1.1.49.25. doi:10.1137/0221070.
- ^ King, Valerie (1995). A Simpler Minimum Spanning Tree Verification Algorithm. Proceedings of the 4th International Workshop on Algorithms and Data Structures. London, UK, UK: Springer-Verlag. pp. 440–448.