Approximating \(k\)-spanner problems for \(k>2\)
From MaRDI portal
Publication:557826
DOI10.1016/j.tcs.2004.11.022zbMath1075.05082OpenAlexW2044989918MaRDI QIDQ557826
Publication date: 30 June 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.11.022
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
A fast network-decomposition algorithm and its applications to constant-time distributed computation, Collective tree spanners in graphs with bounded parameters, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Approximation of minimum weight spanners for sparse graphs, Activity preserving graph simplification, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Spanners in sparse graphs, Improved Approximation for the Directed Spanner Problem, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Graph spanners: a tutorial review, Distributed Spanner Approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Delaunay graphs are almost as good as complete graphs
- NP-completeness of minimum spanner problems
- The maximum interval number of graphs with given genus
- Graph spanners
- Generating Sparse 2-Spanners
- Distributed Computing: A Locality-Sensitive Approach
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- All-Pairs Almost Shortest Paths
- Generating sparse spanners for weighted graphs
- (1 + εΒ) -spanner constructions for general graphs
- Tree spanners in planar graphs
