School of Technology and Computer Science Seminars
A Lower Bound for Additive Spanners
by Mr. Nithin Varma (School of Technology and Computer Science, TIFR)
Friday, November 9, 2012
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description |
Given an undirected unweighted graph G, a \beta-additive spanner of G is a subgraph H of G in which the shortest distance between any pair of vertices is stretched within an additive factor \beta of their shortest distance in G. The stretch of a subgraph H of G is defined as the stretch of the worst stretched pair in H. It is clear that, the stretch increases as the subgraph gets sparser. In this talk, we'll discuss a lower bound on the number of edges in a spanner having a fixed stretch. |