TY - GEN
T1 - Linear expected-time algorithms for connectivity problems
AU - Karp, Richard M.
AU - Tarjan, Robert Endre
N1 - Funding Information:
*Research partially supported by National Science Foundation Grant MCS-77-09906. ‘Research partially supported by National Science Foundation Grant MCS-7826858 and by Office of Naval Research Contract NOW1476-C-0330. The U.S. Government’s right to retain a nonexclusive royalty-free license in and to the copyright covering this paper, for governmental purposes, is acknowledged.
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. Our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs,
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. Our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs,
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 -