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 proceedingConference contribution

7 Scopus citations

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 languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Ulrike Stege
PublisherSpringer Verlag
Pages363-372
Number of pages10
ISBN (Print)9783319218397
DOIs
StatePublished - 2015
Event14th International Symposium on Algorithms and Data Structures, WADS 2015 - Victoria, Canada
Duration: Aug 5 2015Aug 7 2015

Publication series

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

Other

Other14th International Symposium on Algorithms and Data Structures, WADS 2015
CountryCanada
CityVictoria
Period8/5/158/7/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

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

Fingerprint Dive into the research topics of 'Finding articulation points of large graphs in linear time'. Together they form a unique fingerprint.

Cite this