Buchumschlag

A Lower Bound for Light Spanners in General Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodwin, Greg, Flics, Jeremy
Format:	Preprint
Veröffentlicht:	2024
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

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

An Alternate Proof of Near-Optimal Light Spanners
von: Bodwin, Greg
Veröffentlicht: (2023)

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

Light Edge Fault Tolerant Graph Spanners
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
von: Bodwin, Greg, et al.
Veröffentlicht: (2026)

A Unified View of Graph Regularity via Matrix Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2019)

Improved Online Reachability Preservers
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

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

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

Notes on the Linear Algebraic View of Regularity Lemmas
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

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

Are there graphs whose shortest path structure requires large edge weights?
von: Bernstein, Aaron, et al.
Veröffentlicht: (2023)

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
von: Bodwin, Greg, et al.
Veröffentlicht: (2022)

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

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

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
von: Ahmed, Reyan, et al.
Veröffentlicht: (2024)

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

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

Dynamic Light Spanners in Doubling Metrics
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

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

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

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

Maintaining Light Spanners via Minimal Updates
von: Khodabandeh, Hadi, et al.
Veröffentlicht: (2024)

A Tight Lower Bound for Cycle Detection in Grid Graphs
von: Au, Andrew
Veröffentlicht: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
von: La, An, et al.
Veröffentlicht: (2025)

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

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

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

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

Greedy Completion for Weighted $(α,β)$-Spanners
von: Tzalik, Elad
Veröffentlicht: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
von: He, Jialin, et al.
Veröffentlicht: (2025)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Lightweight Near-Additive Spanners
von: Gitlitz, Yuval, et al.
Veröffentlicht: (2024)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
von: Qi, Chuhan
Veröffentlicht: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
von: Kothari, Pravesh, et al.
Veröffentlicht: (2024)

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

The Complexity of Geodesic Spanners
von: de Berg, Sarita, et al.
Veröffentlicht: (2023)