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 - Funding Information:
This research was supported in part by NSF grants CNS-1408782, IIS-1247750 and by Ministry of Science and Technology, Taiwan, Grant MOST 103-2221-E-001-033.
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 -