Linear expected-time algorithms for connectivity problems

Richard M. Karp; Robert Endre Tarjan

doi:10.1016/0196-6774(80)90017-6

Linear expected-time algorithms for connectivity problems

Richard M. Karp, Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	374-393
Number of pages	20
Journal	Journal of Algorithms
Volume	1
Issue number	4
DOIs	https://doi.org/10.1016/0196-6774(80)90017-6
State	Published - Dec 1980
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(80)90017-6

Cite this

@article{201018abe1fb4f27911972657da2dea4,

title = "Linear expected-time algorithms for connectivity problems",

abstract = "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{\"o}s and Renyi. All the algorithms are optimum to within a constant factor.",

author = "Karp, {Richard M.} and Tarjan, {Robert Endre}",

note = "Funding Information: *Research partially supported by National Science Foundation Grant MCS-77-09906. {\textquoteleft}Research partially supported by National Science Foundation Grant MCS-7826858 and by Office of Naval Research Contract NOW1476-C-0330. The U.S. Government{\textquoteright}s right to retain a nonexclusive royalty-free license in and to the copyright covering this paper, for governmental purposes, is acknowledged.",

year = "1980",

month = dec,

doi = "10.1016/0196-6774(80)90017-6",

language = "English (US)",

volume = "1",

pages = "374--393",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

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/12

Y1 - 1980/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38549130040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38549130040&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(80)90017-6

DO - 10.1016/0196-6774(80)90017-6

M3 - Article

AN - SCOPUS:38549130040

SN - 0196-6774

VL - 1

SP - 374

EP - 393

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 4

ER -

Linear expected-time algorithms for connectivity problems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this