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.

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 -