Finding Articulation Points of Large Graphs in Linear Time

DOI10.1007/978-3-319-21840-3_30zbMath1451.68201OpenAlexW2395939851MaRDI QIDQ3449834

Meng Li, Martín Farach-Colton, Tsan-sheng Hsu, 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

linear-time algorithmarticulation pointssemi-streaming algorithmspace lower bound

Mathematics Subject Classification ID

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

Related Items (1)

Depth First Search in the Semi-streaming Model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superlinear lower bounds for multipass graph processing
• The level ancestor problem simplified
• On graph problems in a semi-streaming model
• Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Graph Distances in the Data-Stream Model
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Computing the Degeneracy of Large Graphs

This page was built for publication: Finding Articulation Points of Large Graphs in Linear Time