A Lower Bound for Additive Spanners



Friday, 9 November 2012, 15:00 to 16:30



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.