Tel-Aviv University - Computer Science Colloquium
Sunday, December 6, 14:15-15:15
at 14:00 We present two new algorithms for solving the ALL PAIRS SHORTEST PATHS (APSP) problem for weighted DIRECTED graphs with small integer weights. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in O(n^{2.575}) time. This improves an algorithm of Alon, Galil and Margalit whose running time is O(n^{2.688}). (The constant 2.575 is derived from the best available bounds on the complexity of rectangular matrix multiplications.) The second algorithm solves the APSP problem ALMOST exactly for directed graphs with ARBITRARY non-negative weights. The algorithm runs in O( (n^\omega/\epsilon) \log (W/\epsilon) ) time, where \omega<2.376 is the exponent of (square) matrix multiplication, \epsilon>0 is an error parameter, and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. The algorithm returns estimates of all the distances in the graph with a stretch of at most (1+\epsilon). Corresponding paths can also be found efficiently. The running time of the algorithm is almost best possible.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html