Fully dynamic biconnectivity in graphs

DOI10.1007/BF01189067MaRDI QIDQ1892579zbMATH OpenFDO

Authors Monika R. Henzinger

Publication date 19 June 1995

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

graph algorithmsgraph connectivitydynamic algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1256640
• Maintaining bridge-connected and biconnected components on-line
• Improved Data Structures for Fully Dynamic Biconnectivity
• Dynamic 2- and 3-connectivity on planar graphs
• scientific article; zbMATH DE number 176746

Cites work

• scientific article; zbMATH DE number 432745 (Why is no real title available?)
• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• scientific article; zbMATH DE number 176746 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• A data structure for dynamic trees
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Depth-First Search and Linear Graph Algorithms
• Maintaining bridge-connected and biconnected components on-line
• On-line algorithms for polynomially solvable satisfiability problems
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Separator based sparsification for dynamic planar graph algorithms

Cited in

(12)

• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
• Biconnectivity approximations and graph carvings
• Generalized core maintenance of dynamic bipartite graphs
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Maintaining bridge-connected and biconnected components on-line
• A topological approach to dynamic graph connectivity
• Improved Data Structures for Fully Dynamic Biconnectivity
• scientific article; zbMATH DE number 1471729 (Why is no real title available?)
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• scientific article; zbMATH DE number 176746 (Why is no real title available?)
• Improved data structures for fully dynamic biconnectivity

This page was built for publication: Fully dynamic biconnectivity in graphs

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