Chennai Mathematical Institute


2.00 p.m.
Small Stretch Pairwise Spanners

Kavitha Telikepalli
TIFR, Mumbai.


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.