Improved Data Structures for Fully Dynamic Biconnectivity

DOI10.1137/S0097539794263907MaRDI QIDQ4507325zbMATH OpenFDO

Authors Monika R. Henzinger

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://infoscience.epfl.ch/record/99359

zbMATH Keywords

biconnectivitydata structuresdynamic graph algorithms

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved data structures for fully dynamic biconnectivity
• Fully dynamic biconnectivity in graphs
• Maintaining bridge-connected and biconnected components on-line
• scientific article; zbMATH DE number 1256640
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs

Cited in

(13)

• Maintaining bridge-connected and biconnected components on-line
• Fully dynamic biconnectivity in graphs
• Improved data structures for fully dynamic biconnectivity
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• A survey on combinatorial optimization in dynamic environments
• scientific article; zbMATH DE number 176746 (Why is no real title available?)
• scientific article; zbMATH DE number 1256640 (Why is no real title available?)
• Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
• Simpler and faster biconnectivity augmentation
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Worst-case deterministic fully-dynamic biconnectivity in changeable planar embeddings
• Recent advances in fully dynamic graph algorithms (invited talk)

This page was built for publication: Improved Data Structures for Fully Dynamic Biconnectivity

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