Cover Image

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meierhans, Simon, Gutenberg, Maximilian Probst
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

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
by: Kyng, Rasmus, et al.
Published: (2025)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
by: Bhattacharya, Sayan, et al.
Published: (2025)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Optimal Electrical Oblivious Routing on Expanders
by: Florescu, Cella, et al.
Published: (2024)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
by: Swartworth, William, et al.
Published: (2025)

Bootstrapping Dynamic APSP via Sparsification
by: Kyng, Rasmus, et al.
Published: (2024)

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
by: Mao, Xiao
Published: (2023)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
by: Mazziane, Younes Ben, et al.
Published: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

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

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Beyond Worst Case Local Computation Algorithms
by: Biswas, Amartya Shankha, et al.
Published: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

On Thin Perfect Matchings up to Polylogarithmic Factors
by: Haqi, Alireza, et al.
Published: (2026)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
by: Szyfelbein, Michał, et al.
Published: (2026)

Reviving Thorup's Shortcut Conjecture
by: Bernstein, Aaron, et al.
Published: (2025)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
by: Dufay, Marc, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)