Finding Minimum Spanning Trees
David R. Cheriton, Robert Endre Tarjan · SIAM Journal on Computing · 1976
This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with $O(m\log \log n)$ worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense graphs (those for which m is $\Omega (n^{1 + \varepsilon } )$ for some positive constant $\varepsilon $); 3. an $O(n)$ worst-case algorithm for planar graphs; 4. relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.