Linear expected-time algorithms for connectivity problems

Richard M. Karp, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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,

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980
PublisherAssociation for Computing Machinery
Pages368-377
Number of pages10
ISBN (Electronic)0897910176
DOIs
StatePublished - Apr 28 1980
Externally publishedYes
Event12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States
Duration: Apr 28 1980Apr 30 1980

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume1980-April
ISSN (Print)0737-8017

Other

Other12th Annual ACM Symposium on Theory of Computing, STOC 1980
CountryUnited States
CityLos Angeles
Period4/28/804/30/80

All Science Journal Classification (ASJC) codes

  • Software

Cite this

Karp, R. M., & Tarjan, R. E. (1980). Linear expected-time algorithms for connectivity problems. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980 (pp. 368-377). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April). Association for Computing Machinery. https://doi.org/10.1145/800141.804686