2.00 p.m. Small Stretch Pairwise Spanners Kavitha Telikepalli TIFR, Mumbai. 26-09-12 Abstract Let G be an undirected unweighted graph and let P be a subset of pairs of vertices. We consider the problem of computing a sparse subgraph H of G such that for every pair (u,v) in P, the u-v stretch in H is small. That is, the u-v distance in H is close to the u-v distance in G. We show efficient algorithms to compute such sparse subgraphs where all pairs in P suffer a small additive stretch.
|