On shortest paths avoiding single node failure

size data structure so that the following query can be answered
efficiently.
D(u,v,x) : report the distance from u to v when the vertex x has been
removed.

There is a trivial O(n^3) space data structure for
this problem. The real challenge lies in using smaller space and faster
preprocessing time for the data structure. In the recent past there have
been many efficient algorithms for this and related problems. Recently
Bernstein and Karger (STOC 2009) showed that it is possible to achieve
O(n^2 log n) space and O(mn polylog n) time, and O(1) query time for all
pairs shortest paths under single node failure.

There are three objectives of the talk :
1. To present an overview of the problems and algorithms for shortest path
problem under single node failure.
2. To present (our) new algorithms for single source approximate shortest
paths under single node failure.
3. To present open problems and an invitation for collaboration.

All interested are welcome to attend. No prerequisite is required for the
talk.