Linear expected-time algorithms for connectivity problems

Richard M. Karp; Robert Endre Tarjan

doi:10.1145/800141.804686

Linear expected-time algorithms for connectivity problems

Richard M. Karp, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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 language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980
Publisher	Association for Computing Machinery
Pages	368-377
Number of pages	10
ISBN (Electronic)	0897910176
DOIs	https://doi.org/10.1145/800141.804686
State	Published - Apr 28 1980
Externally published	Yes
Event	12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States Duration: Apr 28 1980 → Apr 30 1980

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	1980-April
ISSN (Print)	0737-8017

Other

Other	12th Annual ACM Symposium on Theory of Computing, STOC 1980
Country/Territory	United States
City	Los Angeles
Period	4/28/80 → 4/30/80

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800141.804686

Cite this

@inproceedings{f0c4388a15734d58972b92d2bfaf376f,

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

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.",

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

note = "Publisher Copyright: {\textcopyright} 1980 ACM.; 12th Annual ACM Symposium on Theory of Computing, STOC 1980 ; Conference date: 28-04-1980 Through 30-04-1980",

year = "1980",

month = apr,

day = "28",

doi = "10.1145/800141.804686",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "368--377",

booktitle = "Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980",

}

Karp, RM & Tarjan, RE 1980, Linear expected-time algorithms for connectivity problems. in Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 1980-April, Association for Computing Machinery, pp. 368-377, 12th Annual ACM Symposium on Theory of Computing, STOC 1980, Los Angeles, United States, 4/28/80. https://doi.org/10.1145/800141.804686

Linear expected-time algorithms for connectivity problems. / Karp, Richard M.; Tarjan, Robert Endre.
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980. Association for Computing Machinery, 1980. p. 368-377 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Linear expected-time algorithms for connectivity problems

AU - Karp, Richard M.

AU - Tarjan, Robert Endre

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.

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.

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 -

Linear expected-time algorithms for connectivity problems

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this