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.