Dynamic bridge-finding in O(^2 n) amortized time

MaRDI QIDQ4607874zbMATH OpenFDO

Authors Jacob Holm, Eva Rotenberg, Mikkel Thorup

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1707.06311, http://dl.acm.org/citation.cfm?id=3175269

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Maintaining bridge-connected and biconnected components on-line
• Near-optimal fully-dynamic graph connectivity
• Improved data structures for fully dynamic biconnectivity
• Faster deterministic fully-dynamic graph connectivity
• Improved Data Structures for Fully Dynamic Biconnectivity

Cited in

(7)

• scientific article; zbMATH DE number 7359421 (Why is no real title available?)
• One-way trail orientations
• Improved dynamic colouring of sparse graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Good r-divisions imply optimal amortized decremental biconnectivity
• Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
• Tree-packing revisited: faster fully dynamic min-cut and arboricity

This page was built for publication: Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time

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