TY - GEN
T1 - A randomized linear-Time algorithm for finding minimum spanning trees
AU - Kleint, Philip N.
AU - Tarjan, Robert E.
N1 - Funding Information:
Brown Univer sity, Providence, RI 02912-1910. Research partially supported by an NSF PYI award, CCR-9157620, together with PYI matching funds from Thinking Machines Corporation, Xerox Corporation, and Honeywell Corporation. Additional support provided by DARPA Contract No. NOO014-91-J-4052, ARPA Order No. 8225, and by the NEC Research Institute, Princeton, NJ. t Department of Computer Science, Princeton University, Princeton, NJ and the NEC Research Institute, Princeton, NJ. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-S920505; the Office of Naval Research, Contract No. NO014-91-J-1463; and DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science and Technology Center, Grant No. NSF-STC8S-0964S.
Publisher Copyright:
© 1994 ACM.
PY - 1994/5/23
Y1 - 1994/5/23
N2 - We present a randomized linear-Time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-Time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-Access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
AB - We present a randomized linear-Time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-Time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-Access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
UR - http://www.scopus.com/inward/record.url?scp=0027940774&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027940774&partnerID=8YFLogxK
U2 - 10.1145/195058.195084
DO - 10.1145/195058.195084
M3 - Conference contribution
AN - SCOPUS:0027940774
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 9
EP - 15
BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PB - Association for Computing Machinery
T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994
Y2 - 23 May 1994 through 25 May 1994
ER -