Copertina

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

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Holm, Jacob, Nadara, Wojciech, Rotenberg, Eva, Sokołowski, Marek
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Dynamic Detours
di: Dadush, Daniel, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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