[Brown CS Talks] Brown CS Seminar: Mikkel Thorup in Lubrano on 9/27/02 at noon

[talks@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			    Mikkel Thorup
		   
			      AT&T Labs
			
				

		  Friday, September 27, 2002 at noon

	       Lubrano Conference Room (CIT 4th floor)

	       Refreshments will be served at 11:45 am

				
	      On Distance Oracles and Routing in Graphs


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 labeling scheme that can be
used for efficient routing.

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

		     Host: Professor Philip Klein