A randomized linear-time algorithm for finding minimum spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A randomized linear-time algorithm for finding minimum spanning trees

Full text

Pdf (647 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 9 - 15

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Philip N. Klein	Department of Computer Science, Brown University, Providence, RI
Robert E. Tarjan	Department of Computer Science, Princeton University, Princeton, NJ and NEC Research Institute, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 60, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195084 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley # Sons, Inc., New York, N. Y., 1992, p. 223.
	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.
	3	O. Borfivka, "0 jist#m probl4mu minim~1nim, Prdca Moravskd P#rodov#deckd Spole#nosti 3, 1926, pp. 37- 58. (In Czech.)
	4	Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
	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.
	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.
	7	Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
	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.
	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.
	10	H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
	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.
	12	D. R. Karger, "Approximating, verifying, and constructing minimum spanning forests, manuscript, 1992.
	13	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	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.
	15	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	16	V. King, "A simpler minimum spanning tree verification algorithm" manuscript (1993).
	17	J. KomlSs, "Linear verification for spanning trees," Combinatorica 5, 1985, pp. 57-65
	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.
	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.
	20	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
	21	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

CITED BY 7

	Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995
	David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada
	Shay Halperin , Uri Zwick, Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.438-447, January 28-30, 1996, Atlanta, Georgia, United States
	Vincenzo Liberatore, Matroid decomposition methods for the set maxima problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.400-409, January 25-27, 1998, San Francisco, California, United States
	Richard Cole , Philip N. Klein , Robert E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.243-250, June 24-26, 1996, Padua, Italy
	David Alberts , Monika Rauch Henzinger, Average case analysis of dynamic graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.312-321, January 22-24, 1995, San Francisco, California, United States