Abstract: A $t$-{\em spanner} $H$ of a weighted graph $G=(V,E,w)$ is a subgraph that approximates all pairwise distances up to a factor of $t$. The {\em lightness} of $H$ is defined as the ratio between the weight of $H$ to that of the minimum spanning tree. An $(\alpha,\beta)$-{\em Shallow Light Tree} (SLT) is a tree of lightness $\beta$, that approximates all distances from a designated root vertex up to a factor of $\alpha$. A long line of works resulted in efficient algorithms that produce (nearly) optimal light spanners and SLTs. Some of the most no...
(read more)
Topics: 
Combinatorics
Discrete mathematics