Cover Image

The Discrepancy of Shortest Paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodwin, Greg, Deng, Chengyuan, Gao, Jie, Hoppenworth, Gary, Upadhyay, Jalaj, Wang, Chen
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, 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)

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

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

On the Price of Differential Privacy for Hierarchical Clustering
by: Deng, Chengyuan, et al.
Published: (2025)

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

Improved Differentially Private Continual Observation Using Group Algebra
by: Henzinger, Monika, et al.
Published: (2024)

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

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)

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

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

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

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

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

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

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

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)

Near-Optimal Generalized Private Testing
by: Chaturvedi, Anamay, et al.
Published: (2026)

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)

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

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

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

Almost Tight Error Bounds on Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2022)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
by: Dinitz, Michael, et al.
Published: (2025)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

Hierarchical Multicriteria Shortest Path Search
by: Kurbanov, Temirlan, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Binned Group Algebra Factorization for Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)