Approximating \(k\)-spanner problems for \(k>2\)
type: Item
instance of: scholarly article
title: Approximating \(k\)-spanner problems for \(k>2\)
zbMATH Open document ID: 1075.05082
author: Michael Elkin
author: David Peleg
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2184056
zbMATH Keywords: graph algorithm
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.11.022
OpenAlex ID: W2044989918
cites work: Generating sparse spanners for weighted graphs
cites work: Q3852212
cites work: NP-completeness of minimum spanner problems
cites work: Tree Spanners
cites work: NEW SPARSENESS RESULTS ON GRAPH SPANNERS
cites work: Delaunay graphs are almost as good as complete graphs
cites work: All-Pairs Almost Shortest Paths
cites work: Q2728855
cites work: Q2754183
cites work: (1 + εΒ) -spanner constructions for general graphs
cites work: Tree spanners in planar graphs
cites work: Q4400851
cites work: Generating Sparse 2-Spanners
cites work: Q4130999
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Graph spanners
cites work: An Optimal Synchronizer for the Hypercube
cites work: The maximum interval number of graphs with given genus
DOI: 10.1016/J.TCS.2004.11.022
description: scientific article; zbMATH DE number 2184056