Finding articulation points of large graphs in linear time

DOI10.1007/978-3-319-21840-3_30MaRDI QIDQ3449834zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Tsan-sheng Hsu, Meng Li, Meng-Tsung Tsai

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21840-3_30

zbMATH Keywords

articulation pointslinear-time algorithmsemi-streaming algorithmspace lower bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Strong articulation points and strong bridges in large scale graphs
• Optimal per-edge processing times in the semi-streaming model
• Automata, Languages and Programming
• Finding strong bridges and strong articulation points in linear time
• On graph problems in a semi-streaming model

Cites work

• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Computing the degeneracy of large graphs
• Data streams: algorithms and applications.
• Efficiency of a Good But Not Linear Set Union Algorithm
• Graph Distances in the Data-Stream Model
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• Linear programming in the semi-streaming model with application to the maximum matching problem
• On graph problems in a semi-streaming model
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• Superlinear lower bounds for multipass graph processing
• The level ancestor problem simplified

Cited in

(3)

• Linear time construction of indexable elastic founder graphs
• scientific article; zbMATH DE number 1230492 (Why is no real title available?)
• Depth First Search in the Semi-streaming Model

This page was built for publication: Finding articulation points of large graphs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449834)