# ICS 269, Spring 2002: Theory Seminar

## 3 May 2002:

Oracles for Distances Avoiding a Link-failure,
by Camil Demetrescu and Mikkel Thorup, SODA 2002.

Speaker: Jonathan Sun

Abstract: Two queries are considered in a directed graph G:
*distance*(x,y,u,v) that returns the shortest distance from x to y in G
that does not contain edge (u,v); *path*(x,y,u,v) that returns the
shortest path, if any, from x to y in G that does not contain edge
(u,v). The authors show two oracles, one with query time O(logn) and
space O(n^2 logn) and the other with query time O(1) and space O(n^2.5).