Campus Event Calendar

Event Entry

What and Who

Algorithms for approximate shortest paths in weighted graphs : Improvement from Sub-cubic to Quadratic time

Surender Baswana
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Tuesday, 4 October 2005
45 Minutes
46.1 - MPII


The all-pairs approximate shortest-paths problem is an interesting

variant of the classical all-pairs shortest-paths problem in graphs.
The problem aims at building a data-structure for a given graph
with the following two features. Firstly, for any two vertices,
it should report an *approximate* shortest path between them,
that is, a path which is longer than the shortest path
by some *small* factor. Secondly, the data-structure should require
less preprocessing time (strictly sub-cubic) and occupy optimal space
(sub-quadratic), at the cost of this approximation.
In the last ten years a number of algorithms have been designed for computing all-pairs approximate shortest paths. In the recent workshop ADFOCS05, Uri Zwick gave a excellent tutorial on some of these algorithms.

In this talk, we shall present significantly improved algorithms for computing all-pairs approximate shortest paths in weighted graphs. The improvement in the running time is from sub-cubic to quadratic, and this also answers one of the open question in this area.

This is a joint work with Kavitha Telikepalli.


Surender Baswana
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Shortest-path, Distance

Surender Baswana, 09/30/2005 15:50 -- Created document.