Fully dynamic biconnectivity in graphs

DOI10.1007/BF01189067zbMATH Open0826.68097MaRDI QIDQ1892579FDOQ1892579

Authors: Monika R. Henzinger 

Publication date: 19 June 1995

Published in: Algorithmica (Search for Journal in Brave)

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

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)

Cites Work

• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• A data structure for dynamic trees
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Separator based sparsification for dynamic planar graph algorithms
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• On-line algorithms for polynomially solvable satisfiability problems
• Maintaining bridge-connected and biconnected components on-line
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• 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
• Improved Data Structures for Fully Dynamic Biconnectivity
• A topological approach to dynamic graph connectivity
• Title not available (Why is that?)
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Title not available (Why is that?)
• Improved data structures for fully dynamic biconnectivity
• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain 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)