@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",
}