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

DOI10.1016/j.tcs.2004.11.022zbMath1075.05082OpenAlexW2044989918MaRDI QIDQ557826

Michael Elkin, David Peleg

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

zbMATH Keywords

graph algorithmapproximation

Mathematics Subject Classification ID

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 (12)

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

This page was built for publication: Approximating \(k\)-spanner problems for \(k>2\)