The hardness of approximating spanner problems

DOI10.1007/3-540-46541-3_31MaRDI QIDQ2728855zbMATH OpenFDO

Authors Michael Elkin, David Peleg

Publication date 1 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46541-3_31

zbMATH Keywords

approximation algorithmsgraph spannershardness of approximationvariants of the sparse \(k\)-spanner problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99) Approximation algorithms (68W25)

Recommendations

• The hardness of approximating spanner problems
• On the hardness of approximating spanners
• On the hardness of approximating spanners
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Approximating \(k\)-spanner problems for \(k>2\)
• scientific article; zbMATH DE number 1757950
• NP-completeness of minimum spanner problems
• On the hardness of computing span of subcubic graphs
• scientific article; zbMATH DE number 1330076
• Lowest-degree k-spanner: approximation and hardness

Cited in

(12)

• NP-completeness of minimum spanner problems
• The hardness of approximating spanner problems
• scientific article; zbMATH DE number 1670859 (Why is no real title available?)
• Lowest-degree k-spanner: approximation and hardness
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• On the hardness of approximating spanners
• scientific article; zbMATH DE number 1757950 (Why is no real title available?)
• Approximating \(k\)-spanner problems for \(k>2\)
• On the hardness of approximating spanners
• Domination and coverage problems under vulnerability constraints
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• On the positive-negative partial set cover problem

This page was built for publication: The hardness of approximating spanner problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2728855)