Tata Institute of Fundamental Research
A Lower Bound for Additive Spanners
Student Seminar
Speaker:
Nithin M. Varma
Organiser:
Shishir Pandey
Date:
Friday, 9 Nov 2012, 15:00 to 16:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Nithin M. Varma |
| Organiser: | Shishir Pandey |
| Date: | Friday, 9 Nov 2012, 15:00 to 16:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.