Fully dynamic biconnectivity in ðª ~ â¡ ( log 2 â¡ n ) \BigOTilde(\log^{2}n) time
Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek SokoÅowski · 2025
Read Fully dynamic biconnectivity in ðª ~ â¡ ( log 2 â¡ n ) \BigOTilde(\log^{2}n) time by Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek SokoÅowski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21733.txt.
Description
Jacob Holm, Wojciech Nadara, Eva Rotenberg and Marek SokoÅowski maintain biconnectivity in a graph that keeps changing, in their 2025 arXiv paper. Cut vertices, whose removal disconnects the graph, matter for network reliability. Their deterministic data structure handles edge insertions and deletions and answers whether two vertices are biconnected or names a vertex separating them.
Updates run in roughly log-squared time, matching the best deterministic dynamic connectivity results up to small factors. The speedup comes through a chain of reductions plus new tricks: a cheaper read-only expose operation on top trees and a biased disjoint-set structure that may interest others. Neighbor data structures with preferred VIP neighbors save the final factors.
Catalog record
| CREATOR | Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek SokoÅowski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 267 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21733