A randomized linear-Time algorithm for finding minimum spanning trees

Philip N. Kleint, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Pages9-15
Number of pages7
ISBN (Electronic)0897916638
DOIs
StatePublished - May 23 1994
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129502
ISSN (Print)0737-8017

Other

Other26th Annual ACM Symposium on Theory of Computing, STOC 1994
CountryCanada
CityMontreal
Period5/23/945/25/94

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'A randomized linear-Time algorithm for finding minimum spanning trees'. Together they form a unique fingerprint.

Cite this