New Algorithms for All Pairs Approximate Shortest Paths

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 (minn3/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.