New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty · 2023
Let G=(V,E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an (min{n3/2m1/2,n7/3 })-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong [ICALP 2022] improved the running time for dense graphs to (n2.29)-time, using FMM, where an exact solution can be computed with FMM in (nω) time (ω < 2.37286) using Seidel’s algorithm.