Approximate shortest paths in weighted graphs

Yuster, Raphael

Open PDF

Open link

Publication date

March 2012

DOI

10.1016/j.jcss.2011.09.001

Publisher

Elsevier Inc.

ISSN

0022-0000

Citation count (estimate)

Abstract

AbstractWe present an approximation algorithm for the all pairs shortest paths (APSP) problem in weighed graphs. Our algorithm solves the APSP problem for weighted directed graphs, with real (positive or negative) weights, up to an additive error of ϵ. For any pair of vertices u,v, the algorithm finds a path whose length is at most δ(u,v)+ϵ. The algorithm is randomized and runs in O˜(n(ω+3)/2)<O(n2.688) time, where n is the number of vertices and ω is the matrix multiplication exponent. The absolute weights are allowed to mildly depend upon n, being at most no(1) (we note that even if the weights are constants, δ(u,v) can be linear in n, while the error requirement ϵ is a small constant independent of n). Clearly, ϵ-additive approximations ...