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.

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
Country/TerritoryUnited States
CityLos Angeles
Period4/28/804/30/80

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Linear expected-time algorithms for connectivity problems'. Together they form a unique fingerprint.

Cite this