Cover Image

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Holm, Jacob, Nadara, Wojciech, Rotenberg, Eva, Sokołowski, Marek
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

Fast decremental tree sums in forests
by: Berendsohn, Benjamin Aram, et al.
Published: (2026)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
by: Leung, Yui Hin Arvin
Published: (2025)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
by: Papadopoulos, Kleitos
Published: (2026)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Dynamic Detours
by: Dadush, Daniel, et al.
Published: (2026)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
by: van der Hoog, Ivor, et al.
Published: (2025)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Simpler Optimal Sorting from a Directed Acyclic Graph
by: van der Hoog, Ivor, et al.
Published: (2024)

Sparsity-Parameterised Dynamic Edge Colouring
by: Christiansen, Aleksander B. G., et al.
Published: (2023)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
by: Jaffke, Lars, et al.
Published: (2025)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
by: Bourneuf, Romain, et al.
Published: (2025)

Near-Optimal Heaps and Dijkstra on Pointer Machines
by: van der Hoog, Ivor, et al.
Published: (2026)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Building a Balanced k-d Tree in O(kn log n) Time
by: Brown, Russell A.
Published: (2014)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Private graph colouring with limited defectiveness
by: Christiansen, Aleksander B. G., et al.
Published: (2024)

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
by: Jędrzejczak, Patryk, et al.
Published: (2025)

Space-efficient SLP encoding for $O(\log N)$-time random access
by: Takasaka, Akito, et al.
Published: (2024)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

Learning Multinomial Logits in $O(n \log n)$ time
by: Chierichetti, Flavio, et al.
Published: (2026)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

String Indexing for Top-$k$ Close Consecutive Occurrences
by: Bille, Philip, et al.
Published: (2020)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
by: Großmann, Ernestine, et al.
Published: (2025)