Philip N. Klein
Robert E. Tarjan
- 1.N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley # Sons, Inc., New York, N. Y., 1992, p. 223.Google Scholar
- 2.M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan, "Time bounds for selection," J. Comput. System Sci. 7, 1973, pp. 448-461.Google ScholarDigital Library
- 3.O. Borfivka, "0 jist#m probl4mu minim~1nim, Prdca Moravskd P#rodov#deckd Spole#nosti 3, 1926, pp. 37- 58. (In Czech.)Google Scholar
- 4.J. Cheriyan, T. Hagerup, and K. Mehlhorn, "Can a maximum flow be computed in O(nm) time?", Proc. 17th International Colloquium on Automata, Languages, and Programming, published as Lecture Notes in Computer Science, Vol. 443, Springer- Verlag, New York, 1990, pp. 235-248. Google ScholarDigital Library
- 5.R. Cole, P. N. Klein, and R. E. Tarjan, "A linear-work parallel algorithm for finding minimum spanning trees," to appear in Proc., 6th Symposium on Parallel Algorithms and Architectures, 1994.Google Scholar
- 6.R. Cole and U. Vishkin, "Approximate and exact parallel scheduling with applications to list, tree, and graph problems," Proc. 27th Annual IEEE Syrup. on Foundations of Computer Science, Computer Society Press, Los Alamitos, CA, 1986, pp. 478-491.Google Scholar
- 7.B. Dixon, M. Rauch, and R. E. Tarjan, "Verification and sensitivity analysis of minimum spanning trees in linear time," SIAM J. on Computing 21, 1992, pp. 1184-1192. Google ScholarDigital Library
- 8.M. Fredman and D. E. Willard, "Transdichotomous algorithms for minimum spanning trees and shortest paths," Proc. 31st Annual IEEE Syrup. on Foundations of Computer Science, IEEE IEEE Computer Society Press, Los Alamitos# CA, 1990, pp. 719-725.Google Scholar
- 9.H. N. Gabow, Z. Galil, and T. H. Spencer, "Efficient implementation of graph algorithms using contraction," Proc. 25th Annual IEEE Syrup. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1984, pp. 347-357.Google Scholar
- 10.H. N. Gabow, Z. GaUl, T. Spencer, and R. E. Tarjan, "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs," Combinatorica 6, 1986, pp. 109-122. Google ScholarDigital Library
- 11.R. L. Graham and P. Hell, "On the history of the minimum spanning tree problem," Annals of the History of Computing 7, 1985, pp. 43-57.Google ScholarDigital Library
- 12.D. R. Karger, "Approximating, verifying, and constructing minimum spanning forests, manuscript, 1992.Google Scholar
- 13.D. R. Karger, "Global rain-cuts in RNC and other ramifications of a simple mincut algorithm," Proc. 4th Annual A CM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, New York, NY, and Society for Industrial and Applied Mathematics, Philadelphia, PA, 1993, pp. 21-30. Google ScholarDigital Library
- 14.D. R. Karger "Random sampling in matroids, with applications to graph connectivity and minimum spanning trees," Proc. 34st Annual IEEE Syrup. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 84-93.Google Scholar
- 15.R. M. Karp and V. Ramachandran, "A survey of parallel algorithms for sharedmemory machines," Chapter 17 in Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity J. van Leeuwen, ed., MIT Press, Cambridge, Mass., 1990, pp. 869-941. Google ScholarDigital Library
- 16.V. King, "A simpler minimum spanning tree verification algorithm" manuscript (1993).Google Scholar
- 17.J. KomlSs, "Linear verification for spanning trees," Combinatorica 5, 1985, pp. 57-65Google ScholarCross Ref
- 18.J. B. KruskM, "On the shortest spanning subtree of a graph and the traveling salesman problem," Proc. Amer. Math Soc. 7, 1956, pp. 48-50.Google ScholarCross Ref
- 19.P. Raghavan, "Lecture Notes on Randomized Algorithms," Research Report RC 15340 (#68237), Computer Science/Mathematics IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, 1990, p. 54.Google Scholar
- 20.It. E. Tarjan, "Applications of path compression on balanced trees," J. Assoc. Comput. Mach. 26, 1979, pp. 690-715. Google ScholarDigital Library
- 21.R. E. Tarjan, Data Structures and Network Algorithms, Chapter 6, Society for Industrial and Applied Mathematics, Philadelphia, 1983. Google ScholarDigital Library
Index Terms
- A randomized linear-time algorithm for finding minimum spanning trees
Recommendations
A randomized linear-time algorithm to find minimum spanning trees
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning ...
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...
Comments