Buchumschlag

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chuzhoy, Julia, Parter, Merav
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
von: Parter, Merav, et al.
Veröffentlicht: (2025)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
von: Gil, Yuval, et al.
Veröffentlicht: (2025)

Distributed Interactive Proofs for Planarity with Log-Star Communication
von: Gil, Yuval, et al.
Veröffentlicht: (2025)

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
von: Fischer, Orr, et al.
Veröffentlicht: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2025)

Light Spanners with Small Hop-Diameter
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Distributed Maximum Flow in Planar Graphs
von: Abd-Elhaleem, Yaseen, et al.
Veröffentlicht: (2024)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

A Simple Dynamic Spanner via APSP
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

Minimum Temporal Spanners in Happy Graphs
von: Casteigts, Arnaud, et al.
Veröffentlicht: (2026)

Multiplicative Spanners in Minor-Free Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
von: Li, Jason, et al.
Veröffentlicht: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2021)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2026)

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Routing-Controlled Spanners
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

New Greedy Spanners and Applications
von: Popova, Elizaveta, et al.
Veröffentlicht: (2026)

Directed Buy-at-Bulk Spanners
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

Fully Dynamic Algorithms for Chamfer Distance
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Fully Dynamic Algorithms for Transitive Reduction
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Diameter Computation on (Random) Geometric Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2026)

Diameter Shortcut Sets on Temporal Graphs
von: Quantmeyer, Gerome
Veröffentlicht: (2025)

On Strong Diameter Padded Decompositions
von: Filtser, Arnold
Veröffentlicht: (2019)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
von: Xu, Chao, et al.
Veröffentlicht: (2026)

Almost-Optimal Sublinear Additive Spanners
von: Tan, Zihan, et al.
Veröffentlicht: (2023)

A Unified Framework for Hopsets and Spanners
von: Neiman, Ofer, et al.
Veröffentlicht: (2021)

Shortcuts and Transitive-Closure Spanners Approximation
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)