Approximating k-spanner problems for k>2
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.
- (1 + εΒ) -spanner constructions for general graphs
- All-Pairs Almost Shortest Paths
- An Optimal Synchronizer for the Hypercube
- Delaunay graphs are almost as good as complete graphs
- Distributed Computing: A Locality-Sensitive Approach
- Generating Sparse 2-Spanners
- Generating sparse spanners for weighted graphs
- Graph spanners
- scientific article; zbMATH DE number 1629828 (Why is no real title available?)
- scientific article; zbMATH DE number 1670859 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 1182768 (Why is no real title available?)
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- NP-completeness of minimum spanner problems
- The maximum interval number of graphs with given genus
- Tree Spanners
- Tree spanners in planar graphs
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Graph spanners: a tutorial review
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Activity preserving graph simplification
- scientific article; zbMATH DE number 1629828 (Why is no real title available?)
- scientific article; zbMATH DE number 1670859 (Why is no real title available?)
- scientific article; zbMATH DE number 6696497 (Why is no real title available?)
- Improved approximation for the directed spanner problem
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Generating Sparse 2-Spanners
- scientific article; zbMATH DE number 2038725 (Why is no real title available?)
- scientific article; zbMATH DE number 1757950 (Why is no real title available?)
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- Distributed spanner approximation
- Generating sparse 2—spanners
- Approximation of minimum weight spanners for sparse graphs
- Spanners in sparse graphs
- Carousel greedy algorithms for the minimum stretch spanning tree problem
- Spanner approximations in practice
- Collective tree spanners in graphs with bounded parameters
This page was built for publication: Approximating \(k\)-spanner problems for \(k>2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557826)
