Degree-Constrained Network Spanners with Nonconstant Delay
Arthur L. Liestman, Thomas Caton Shermer · SIAM Journal on Discrete Mathematics · 1995
A spanning subgraph $S = ( V,E^\prime )$ of a connected simple graph $G = ( V,E )$ is a $f( x )$-spanner if for any pair of nodes u and $v $, $d_S ( u,v ) \leq f ( d_G ( u,v ) )$ where $d_G $ and $d_S $ are the usual distance functions in graphs G and S, respectively. The delay of the $f( x )$-spanner is $f( x ) - x$. In this paper $( 2.5\sqrt {( 3x + 6 )/4} + 6 + x )$-spanners for two-dimensional grids with maximum degree 3 are found and it is proven that the delay of these spanners is within a constant factor of optimal. A $( \frac{1}{k}x + k + 8 - \frac{7}{k} + x )$-spanner of the X-tree with maximum degree 3 is described, and it is proven that the delay of this spanner is within a constant factor of optimal. In addition, a $( 2 + x )$-spanner of the pyramid with maximum degree 6 and a $( \frac{1}{k}x + k + 8 - \frac{7}{k} + x )$-spanner of the pyramid with maximum degree 5 are described, and it is proven that the delay of the latter spanner is within a constant factor of optimal.