Copertina

A Simple Dynamic Spanner via APSP

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kyng, Rasmus, Meierhans, Simon, Zöcklein, Gernot
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Bootstrapping Dynamic APSP via Sparsification
di: Kyng, Rasmus, et al.
Pubblicazione: (2024)

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

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

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
di: Goranci, Gramoz, et al.
Pubblicazione: (2026)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
di: Grunau, Christoph, et al.
Pubblicazione: (2025)

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

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

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
di: Adil, Deeksha, et al.
Pubblicazione: (2024)

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

Improved Additive Approximation Algorithms for APSP
di: Jin, Ce, et al.
Pubblicazione: (2025)

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

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
di: Nogler, Jakob, et al.
Pubblicazione: (2024)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
di: Koo, Jaehyun
Pubblicazione: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
di: Fischer, Nick
Pubblicazione: (2026)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2025)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
di: Chuzhoy, Julia, et al.
Pubblicazione: (2026)

Routing-Controlled Spanners
di: Grigorescu, Elena, et al.
Pubblicazione: (2024)

A Unified Framework for Hopsets and Spanners
di: Neiman, Ofer, et al.
Pubblicazione: (2021)

Directed Buy-at-Bulk Spanners
di: Grigorescu, Elena, et al.
Pubblicazione: (2024)

New Greedy Spanners and Applications
di: Popova, Elizaveta, et al.
Pubblicazione: (2026)

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

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
di: Roditty, Liam, et al.
Pubblicazione: (2025)

Graph Spanners for Group Steiner Distances
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Minimum Temporal Spanners in Happy Graphs
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

Multiplicative Spanners in Minor-Free Graphs
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Approximate Light Spanners in Planar Graphs
di: Le, Hung, et al.
Pubblicazione: (2025)

Almost-Optimal Sublinear Additive Spanners
di: Tan, Zihan, et al.
Pubblicazione: (2023)

Shortcuts and Transitive-Closure Spanners Approximation
di: Chalermsook, Parinya, et al.
Pubblicazione: (2025)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
di: Bhore, Sujoy, et al.
Pubblicazione: (2024)

Dynamic Light Spanners in Doubling Metrics
di: Bhore, Sujoy, et al.
Pubblicazione: (2026)

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

A Lower Bound for Light Spanners in General Graphs
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Greedy Completion for Weighted $(α,β)$-Spanners
di: Tzalik, Elad
Pubblicazione: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
di: He, Jialin, et al.
Pubblicazione: (2025)

Lightweight Near-Additive Spanners
di: Gitlitz, Yuval, et al.
Pubblicazione: (2024)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
di: Ahmed, Reyan, et al.
Pubblicazione: (2024)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
di: Qi, Chuhan
Pubblicazione: (2025)

Maintaining Light Spanners via Minimal Updates
di: Khodabandeh, Hadi, et al.
Pubblicazione: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
di: Bodwin, Greg, et al.
Pubblicazione: (2024)