@inproceedings{67275eac041c46c49dde3ad699ded037,

title = "A randomized linear-Time algorithm for finding minimum spanning trees",

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.",

author = "Kleint, {Philip N.} and Tarjan, {Robert E.}",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 26th Annual ACM Symposium on Theory of Computing, STOC 1994 ; Conference date: 23-05-1994 Through 25-05-1994",

year = "1994",

month = may,

day = "23",

doi = "10.1145/195058.195084",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "9--15",

booktitle = "Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994",

}