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.
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.