Approximating \(k\)-spanner problems for \(k>2\) (Q557826)

The basic \(k\)-spanner problem is to find a sparse spanning subgraph \(H\) of the input graph \(G\) such that \(d_H(x,y) \leq k \cdot d_G(x,y)\) for all vertices \(x\) and \(y\). For this problem and variants thereof the authors list known (in-)approximability results, and generalise the technique of \textit{G. Kortsarz} and \textit{D. Peleg} [J. Algorithms 17, 222--236 (1994)] to \(k>2\). See [Integer programming and combinatorial optimization. 8th international IPCO conference, Utrecht, Netherlands, June 13--15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2081, 90--104 (2001; Zbl 0987.68052)] for a summary of the preceding conference version.