| 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.
|