Improved data structures for fully dynamic biconnectivity

DOI10.1145/195058.195434MaRDI QIDQ2817663zbMATH OpenOpenAlexFDO

Authors Monika R. Henzinger

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/6194

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

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

Cited in

(18)

• Maintaining bridge-connected and biconnected components on-line
• Lower bounds for fully dynamic connectivity problems in graphs
• Dyn-FO: A parallel, dynamic complexity class
• Decremental 2- and 3-connectivity on planar graphs
• Dynamic connectivity in digital images
• Fully dynamic planarity testing with applications
• Near-optimal fully-dynamic graph connectivity
• Improved Data Structures for Fully Dynamic Biconnectivity
• Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
• Simpler and faster biconnectivity augmentation
• Fully dynamic 2-edge-connectivity in planar graphs
• Lower bounds for dynamic algorithms
• Faster possibility detection by combining two approaches
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• A dynamic algorithm for line graph recognition
• Output-sensitive reporting of disjoint paths (extended abstract)
• An approximation algorithm for minimum-cost vertex-connectivity problems

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 Q2817663)