link

January 7, Wednesday
13:00 – 14:00

Almost Shortest Paths and Spanners
Computer Science seminar
Lecturer : Dr. Michael Elkin
Lecturer homepage : http:///www.math.ias.edu/~elkin/
Affiliation : Yale University
Location : -101/58
Host : Dr. Eitan Bachmat
We will consider the problem of computing (almost) shortest paths in an unweighted undirected graph G=(V,E).

We will focus on a version of this problem in which a subset S of V is given as a part of the input, and the objective is to compute paths P(u,w) for all pairs (u,w) in SxV.

This is one of the most fundamental problems in the area of graph algorithms, and it has numerous practical and theoretical applications. We will present and outline the analysis of our recent near-optimal algorithm for this problem.