Seminar at SMU Delhi
January 25, 2012 (Wednesday) ,
3:30 PM at Webinar
Approximating shortest paths in graphs
Abstract of Talk
Computing all-pairs distances in a graph is a fundamental problem of computer
science but there has been a status quo with respect to
the general problem of weighted directed graphs.
In contrast, there has been a growing interest in the area
of algorithms for approximate shortest paths leading to many interesting
variations of the original problem.
In this talk, we trace some of the fundamental developments like
spanners and distance oracles, their underlying constructions, as well as
their applications to the approximate all-pairs shortest paths.