Monday November 11, 2002

Speaker: Lenore J. Cowen (Tufts)

Title: Compact Routing Schemes In Static and Dynamic Networks

Abstract: Suppose you were going to have a yard sale, and you wished to publish directions. Typically, you would select a major street or landmark and publish directions from all points to the landmark, and then careful directions from the landmark to your location. It turns out that this paradigm is also behind many of the best compact routing schemes, where the "directions" or routing information, are stored locally at each vertex: in the analogy above, this is equivalent to the person having only a short address, and learning directions to his destination from looking at small signs posted at each street corner. We will present our recent compact routing results, and how they relate to the graph-theoretic notion of spanners. If time permits, we will present our newest results in the name-independent model.