Title: On Distance Oracles and Routing in Graphs

Speaker: Mikkel Thorup, ATT Research, Florham Park, NJ

Date: Tuesday, October 29, 2002, 4:30-5:30

Location: DIMACS Seminar Room, CoRE Building, Room 431, Rutgers University, Busch Campus, Piscataway, NJ.

Abstract:

We review two basic problems for graphs:

* Constructing a small space distance oracle that, for any pair (u,v) of nodes, provides a quick and good estimate of the distance from u to v.

* Distributing the distance oracle in a labaling scheme that can be used for efficient routing.

For general graphs, near-optimal trade-offs between space and precission are discussed. Better results for planar and bounded tree-width graphs are also discussed.