@inproceedings{37677d5fa6f648939f9a5fb70e11541f,

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 Meng-Tsung Tsai",

year = "2015",

month = jan,

day = "1",

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

language = "English",

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

address = "Germany",

note = "null ; Conference date: 05-08-2015 Through 07-08-2015",

}