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)

Full work available at URL https://doi.org/10.1007/BF01189067

zbMATH Keywords

dynamic algorithmsgraph algorithmsgraph connectivity

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) 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

• 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
• 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?)
• 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

(15)

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

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)