Linear expected-time algorithms for connectivity problems

Richard M. Karp, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


This paper describes fast average-time algorithms for four graph connectivity problems. Algorithms that run in O(n) average time on n-vertex graphs are developed for finding connected components, strong components, and blocks. An O(m)-time algorithm to find a minimum spanning forest in an m-graph is also presented. The analysis of these algorithms uses the random graph model of Erdös and Renyi. All the algorithms are optimum to within a constant factor.

Original languageEnglish (US)
Pages (from-to)374-393
Number of pages20
JournalJournal of Algorithms
Issue number4
StatePublished - Dec 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


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

Cite this