Abstract
Given an n-node m-edge graph G, the articulation points of graph G can be found in \(\mathcal {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 \(\mathcal {O}(n \mathop {\mathrm {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 \(\mathcal {O}(m+n)\) time using \(\mathcal {O}(n)\) space and one sequential pass of the graph. The previous best algorithm in the semi-streaming model also uses \(\mathcal {O}(n)\) space and one pass, but has running time \(\mathcal {O}(m\alpha (n)+n\log n)\), where \(\alpha \) denotes the inverse of Ackermann function.
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 526–538. Springer, Heidelberg (2011)
Ausiello, G., Firmani, D., Laura, L.: Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components. Network 59(3), 275–288 (2012)
Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: 13th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 623–632. SIAM (2002)
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theoretical Computer Science 321(1), 5–12 (2004)
Farach-Colton, M., Tsai, M.-T.: Computing the degeneracy of large graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 250–260. Springer, Heidelberg (2014)
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoretical Computer Science 348(2), 207–216 (2005)
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM Journal on Computing 38(5), 1709–1727 (2008)
Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. In: 28th Conference on Computational Complexity (CCC), pp. 287–298. IEEE (2013)
Hopcroft, J., Tarjan, R.: Efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)
Muthukrishnan, S.: Data streams: Algorithms and applications. Tech. rep. (2003)
O’Connell, T.C.: A survey of graph algorithms under extended streaming models of computation. In: Fundamental Problems in Computing, pp. 455–476. Springer (2009)
Ruhl, J.M.: Efficient Algorithms for New Computational Models. Ph.D. thesis, Massachusetts Institute of Technology, September 2003
Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215–225 (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Farach-Colton, M., Hsu, Ts., Li, M., Tsai, MT. (2015). Finding Articulation Points of Large Graphs in Linear Time. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)