Maintaining bridge-connected and biconnected components on-line
From MaRDI portal
Publication:1186782
DOI10.1007/BF01758773zbMath0748.68045OpenAlexW2010255818WikidataQ56485277 ScholiaQ56485277MaRDI QIDQ1186782
Jeffery Westbrook, Robert Endre Tarjan
Publication date: 28 June 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758773
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items
Data structures for two-edge connectivity in planar graphs ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ Fully dynamic biconnectivity in graphs ⋮ Dynamic 2- and 3-connectivity on planar graphs ⋮ Fully dynamic 2-edge-connectivity in planar graphs ⋮ 2-vertex connectivity in directed graphs ⋮ SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS ⋮ Decremental 2- and 3-connectivity on planar graphs ⋮ Two sufficient conditions for 2-connected graphs to have proper connection number 2 ⋮ Certificates and fast algorithms for biconnectivity in fully-dynamic graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Parametric matroid interdiction ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Articulation of Transition Systems and Its Application to Petri Net Synthesis ⋮ Representing graphs and hypergraphs by touching polygons in 3D ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Linear bounds for on-line Steiner problems ⋮ Approximating minimum cuts under insertions ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity ⋮ Efficient authenticated data structures for graph connectivity and geometric search problems ⋮ Maintenance of triconnected components of graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Depth First Search in the Semi-streaming Model ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths ⋮ Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis
Uses Software
Cites Work
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Maintenance of 2- and 3-edge-connected components of graphs. I
- A topological approach to dynamic graph connectivity
- Maintaining bridge-connected and biconnected components on-line
- A data structure for dynamic trees
- Incremental convex planarity testing
- An Efficient Parallel Biconnectivity Algorithm
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Amortized Computational Complexity
- On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
- Self-adjusting binary search trees
- Worst-case Analysis of Set Union Algorithms
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- An On-Line Edge-Deletion Problem
- Should Tables Be Sorted?
- Efficiency of a Good But Not Linear Set Union Algorithm
- Depth-First Search and Linear Graph Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
