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.

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 -