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.
Cited by 428 works. doi:10.1137/0205051
Authors
References
- The Design and Analysis of Computer Algorithms
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A note on two problems in connexion with graphs
- Shortest Connection Networks And Some Generalizations
- Depth-First Search and Linear Graph Algorithms
- Time bounds for selection
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient Planarity Testing
- Connectivity in Graphs
- An 0(|E|loglog|V|) algorithm for finding minimum spanning trees