Imagen de Portada

Additive Spanner Lower Bounds with Optimal Inner Graph Structure

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bodwin, Greg, Hoppenworth, Gary, Williams, Virginia Vassilevska, Wein, Nicole, Xu, Zixuan
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
por: Bodwin, Greg, et al.
Publicado: (2023)

An Alternate Proof of Near-Optimal Light Spanners
por: Bodwin, Greg
Publicado: (2023)

Beyond 2-approximation for k-Center in Graphs
por: Jin, Ce, et al.
Publicado: (2025)

Are there graphs whose shortest path structure requires large edge weights?
por: Bernstein, Aaron, et al.
Publicado: (2023)

Covering Approximate Shortest Paths with DAGs
por: Assadi, Sepehr, et al.
Publicado: (2025)

Simple Linear-Size Additive Emulators
por: Hoppenworth, Gary
Publicado: (2023)

Detecting Disjoint Shortest Paths in Linear Time and More
por: Akmal, Shyan, et al.
Publicado: (2024)

Light Edge Fault Tolerant Graph Spanners
por: Bodwin, Greg, et al.
Publicado: (2025)

The Discrepancy of Shortest Paths
por: Bodwin, Greg, et al.
Publicado: (2024)

New Separations and Reductions for Directed Preservers and Hopsets
por: Hoppenworth, Gary, et al.
Publicado: (2024)

Shortest Paths in Multimode Graphs
por: Kirkpatrick, Yael, et al.
Publicado: (2025)

Listing 6-Cycles in Sparse Graphs
por: Williams, Virginia Vassilevska, et al.
Publicado: (2024)

Improved Upper Bounds for the Directed Flow-Cut Gap
por: Bodwin, Greg, et al.
Publicado: (2026)

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

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

A Unified View of Graph Regularity via Matrix Decompositions
por: Bodwin, Greg, et al.
Publicado: (2019)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
por: Dalirrooyfard, Mina, et al.
Publicado: (2023)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
por: Nogler, Jakob, et al.
Publicado: (2026)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

Improved Online Reachability Preservers
por: Bodwin, Greg, et al.
Publicado: (2024)

Notes on the Linear Algebraic View of Regularity Lemmas
por: Bodwin, Greg, et al.
Publicado: (2025)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
por: Bodwin, Greg, et al.
Publicado: (2023)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
por: Assadi, Sepehr, et al.
Publicado: (2025)

All-Hops Shortest Paths
por: Williams, Virginia Vassilevska, et al.
Publicado: (2024)

Fast Approximate Counting of Cycles
por: Censor-Hillel, Keren, et al.
Publicado: (2024)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
por: Censor-Hillel, Keren, et al.
Publicado: (2025)

Lightweight Near-Additive Spanners
por: Gitlitz, Yuval, et al.
Publicado: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
por: Chan, Timothy M., et al.
Publicado: (2023)

A Refined Laser Method and Faster Matrix Multiplication
por: Alman, Josh, et al.
Publicado: (2020)

New Diameter Approximations via Distance Oracle Techniques
por: Kirkpatrick, Yael, et al.
Publicado: (2026)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
por: Kirkpatrick, Yael, et al.
Publicado: (2026)

More Asymmetry Yields Faster Matrix Multiplication
por: Alman, Josh, et al.
Publicado: (2024)

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

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

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
por: La, An, et al.
Publicado: (2025)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
por: Chen, Kuowen, et al.
Publicado: (2025)

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

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