Seminar at SMU Delhi

January 25, 2012 (Wednesday) , 3:30 PM at Webinar
Speaker: Sandeep Sen, IIT Delhi
Title: 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.