Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
Abstract
A common step in algorithms related to shortest paths in undirected graphs is that, we select a subset of vertices as centers, then grow a ball around each vertex until a center is reached. We want the balls to be as small as possible. A randomized algorithm can uniformly sample \(r\) centers to achieve the optimal (expected) ball size of \(\Omega (n/r)\). A folklore derandomization is to use the \(O (\log n)\) approximation for the set cover problem in the hitting set version where we want to hit all the balls with the centers.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Facility Location and Emergency Management
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 404–412
- Publication date
- 1 January 2026
- Language
- EN