Improved Additive Approximation Algorithms for APSP
Abstract
The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick [SICOMP’01]. Many recent works have attempted to improve these original algorithms using the algebraic tools of fast matrix multiplication. We improve on these results for the following problems.
Fields of Study & Subjects
Polynomial and algebraic computation
Complexity and Algorithms in Graphs
Graph Theory and Algorithms
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 3639–3651
- Publication date
- 1 January 2026
- Language
- EN