Finding articulation points of large graphs in linear time

Martín Farach-Colton; Tsan Sheng Hsu; Meng Li; Meng Tsung Tsai

doi:10.1007/978-3-319-21840-3_30

Finding articulation points of large graphs in linear time

Martín Farach-Colton, Tsan Sheng Hsu, Meng Li, Meng Tsung Tsai

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

Abstract

Given an n-node m-edge graph G, the articulation points of graph G can be found in O(m + n) time in the RAM model, through a DFS-based algorithm. In the semi-streaming model for large graphs, where memory is limited to O(n polylog n) and edges may only be accessed in one or more sequential passes, no efficient DFS algorithm is known, so another approach is needed. We show that the articulation points can be found in O(m+n) time using O(n) space and one sequential pass of the graph. The previous best algorithm in the semi-streaming model also uses O(n) space and one pass, but has running time O(mα(n)+n log n), where α denotes the inverse of Ackermann function.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Ulrike Stege
Publisher	Springer Verlag
Pages	363-372
Number of pages	10
ISBN (Print)	9783319218397
DOIs	https://doi.org/10.1007/978-3-319-21840-3_30
State	Published - 2015
Event	14th International Symposium on Algorithms and Data Structures, WADS 2015 - Victoria, Canada Duration: Aug 5 2015 → Aug 7 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9214
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Algorithms and Data Structures, WADS 2015
Country/Territory	Canada
City	Victoria
Period	8/5/15 → 8/7/15

Keywords

Articulation points
Linear time algorithm
Semi-streaming algorithm
Space lower bound

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-21840-3_30

Cite this

Farach-Colton, M., Hsu, T. S., Li, M., & Tsai, M. T. (2015). Finding articulation points of large graphs in linear time. In F. Dehne, J.-R. Sack, & U. Stege (Eds.), Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings (pp. 363-372). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9214). Springer Verlag. https://doi.org/10.1007/978-3-319-21840-3_30

Finding articulation points of large graphs in linear time. / Farach-Colton, Martín; Hsu, Tsan Sheng; Li, Meng et al.
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Ulrike Stege. Springer Verlag, 2015. p. 363-372 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9214).

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

Farach-Colton, M, Hsu, TS, Li, M & Tsai, MT 2015, Finding articulation points of large graphs in linear time. in F Dehne, J-R Sack & U Stege (eds), Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9214, Springer Verlag, pp. 363-372, 14th International Symposium on Algorithms and Data Structures, WADS 2015, Victoria, Canada, 8/5/15. https://doi.org/10.1007/978-3-319-21840-3_30

Farach-Colton M, Hsu TS, Li M, Tsai MT. Finding articulation points of large graphs in linear time. In Dehne F, Sack JR, Stege U, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings. Springer Verlag. 2015. p. 363-372. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-21840-3_30

Farach-Colton, Martín ; Hsu, Tsan Sheng ; Li, Meng et al. / Finding articulation points of large graphs in linear time. Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Ulrike Stege. Springer Verlag, 2015. pp. 363-372 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3b138fdbbc7e4a538424d0197aed1533,

title = "Finding articulation points of large graphs in linear time",

abstract = "Given an n-node m-edge graph G, the articulation points of graph G can be found in O(m + n) time in the RAM model, through a DFS-based algorithm. In the semi-streaming model for large graphs, where memory is limited to O(n polylog n) and edges may only be accessed in one or more sequential passes, no efficient DFS algorithm is known, so another approach is needed. We show that the articulation points can be found in O(m+n) time using O(n) space and one sequential pass of the graph. The previous best algorithm in the semi-streaming model also uses O(n) space and one pass, but has running time O(mα(n)+n log n), where α denotes the inverse of Ackermann function.",

keywords = "Articulation points, Linear time algorithm, Semi-streaming algorithm, Space lower bound",

author = "Mart{\'i}n Farach-Colton and Hsu, {Tsan Sheng} and Meng Li and Tsai, {Meng Tsung}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 14th International Symposium on Algorithms and Data Structures, WADS 2015 ; Conference date: 05-08-2015 Through 07-08-2015",

year = "2015",

doi = "10.1007/978-3-319-21840-3_30",

language = "English (US)",

isbn = "9783319218397",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "363--372",

editor = "Frank Dehne and Jorg-Rudiger Sack and Ulrike Stege",

booktitle = "Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings",

}

TY - GEN

T1 - Finding articulation points of large graphs in linear time

AU - Farach-Colton, Martín

AU - Hsu, Tsan Sheng

AU - Li, Meng

AU - Tsai, Meng Tsung

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - Given an n-node m-edge graph G, the articulation points of graph G can be found in O(m + n) time in the RAM model, through a DFS-based algorithm. In the semi-streaming model for large graphs, where memory is limited to O(n polylog n) and edges may only be accessed in one or more sequential passes, no efficient DFS algorithm is known, so another approach is needed. We show that the articulation points can be found in O(m+n) time using O(n) space and one sequential pass of the graph. The previous best algorithm in the semi-streaming model also uses O(n) space and one pass, but has running time O(mα(n)+n log n), where α denotes the inverse of Ackermann function.

AB - Given an n-node m-edge graph G, the articulation points of graph G can be found in O(m + n) time in the RAM model, through a DFS-based algorithm. In the semi-streaming model for large graphs, where memory is limited to O(n polylog n) and edges may only be accessed in one or more sequential passes, no efficient DFS algorithm is known, so another approach is needed. We show that the articulation points can be found in O(m+n) time using O(n) space and one sequential pass of the graph. The previous best algorithm in the semi-streaming model also uses O(n) space and one pass, but has running time O(mα(n)+n log n), where α denotes the inverse of Ackermann function.

KW - Articulation points

KW - Linear time algorithm

KW - Semi-streaming algorithm

KW - Space lower bound

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

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

U2 - 10.1007/978-3-319-21840-3_30

DO - 10.1007/978-3-319-21840-3_30

M3 - Conference contribution

AN - SCOPUS:84951820834

SN - 9783319218397

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 372

BT - Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Stege, Ulrike

PB - Springer Verlag

T2 - 14th International Symposium on Algorithms and Data Structures, WADS 2015

Y2 - 5 August 2015 through 7 August 2015

ER -

Finding articulation points of large graphs in linear time

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this