Algorithms and Complexity Seminar
Thursday, March 20, 2008, 4:00-5:15pm in 32-G575.
Routing with Forbidden Subgraphs
Andy Twigg (Univ. of Cambridge)
I will discuss computing distances and routing with forbidden
subgraphs, in particular for planar graphs. In the model, one can
label vertices of a graph G then must be able to answer distance
queries for any G\X, where X is specified at query time by giving the
labels for vertices in X. The aim is to minimize the label size and
query time. In particular we show an interesting result, that the size
bounds for computing stretch-1 distances around arbitrary subgraphs
match those for simply computing d(u,v) for planar graphs.
Host: Mihai Patrascu
(The Algorithms
and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)