Certificates and fast algorithms for biconnectivity in fully-dynamic graphs

DOI10.1007/3-540-60313-1_142MaRDI QIDQ6102299zbMATH OpenOpenAlexFDO

Authors Monika R. Henzinger, Han La Poutré

Publication date 8 May 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60313-1_142

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1256640
• scientific article; zbMATH DE number 1775391
• Improved Data Structures for Fully Dynamic Biconnectivity
• Fully dynamic planarity testing with applications
• Improved data structures for fully dynamic biconnectivity

Cites work

• Alpha-algorithms for incremental planarity testing (extended abstract)
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• scientific article; zbMATH DE number 1256640 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 1003251 (Why is no real title available?)
• Improved data structures for fully dynamic biconnectivity
• Maintaining bridge-connected and biconnected components on-line
• Separator based sparsification for dynamic planar graph algorithms

Cited in

(7)

• On certificates and lookahead in dynamic graph problems
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• Improved Data Structures for Fully Dynamic Biconnectivity
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Good r-divisions imply optimal amortized decremental biconnectivity
• Dynamic embeddings of dynamic single-source upward planar graphs

This page was built for publication: Certificates and fast algorithms for biconnectivity in fully-dynamic graphs

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