TY - GEN

T1 - Linear expected-time algorithms for connectivity problems

AU - Karp, Richard M.

AU - Tarjan, Robert Endre

N1 - Publisher Copyright:
© 1980 ACM.

PY - 1980/4/28

Y1 - 1980/4/28

N2 - Researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (Exceptions include the work of Angluin and Valiant [1], Karp [7], and Schnorr [9].) In this paper we analyze the expected running time of four algorithms for solving graph connectivity problems.

AB - Researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (Exceptions include the work of Angluin and Valiant [1], Karp [7], and Schnorr [9].) In this paper we analyze the expected running time of four algorithms for solving graph connectivity problems.

UR - http://www.scopus.com/inward/record.url?scp=5644261809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=5644261809&partnerID=8YFLogxK

U2 - 10.1145/800141.804686

DO - 10.1145/800141.804686

M3 - Conference contribution

AN - SCOPUS:5644261809

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 368

EP - 377

BT - Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980

PB - Association for Computing Machinery

T2 - 12th Annual ACM Symposium on Theory of Computing, STOC 1980

Y2 - 28 April 1980 through 30 April 1980

ER -