Cover Image

Multiplicative Spanners in Minor-Free Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodwin, Greg, Hoppenworth, Gary, Tan, Zihan
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

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

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

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

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

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

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

Simple Linear-Size Additive Emulators
by: Hoppenworth, Gary
Published: (2023)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

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

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

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

Improved Online Reachability Preservers
by: Bodwin, Greg, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
by: Bodwin, Greg, et al.
Published: (2022)

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

Routing-Controlled Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

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

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

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

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

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

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

A Separator for Minor-Free Graphs Beyond the Flow Barrier
by: Le, Hung
Published: (2026)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

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

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

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

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

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

Lightweight Near-Additive Spanners
by: Gitlitz, Yuval, et al.
Published: (2024)

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

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