On the hardness of approximating spanners
From MaRDI portal
Publication:5945922
DOI10.1007/s00453-001-0021-yzbMath0985.68041OpenAlexW1997369416MaRDI QIDQ5945922
Publication date: 19 February 2002
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-001-0021-y
Related Items
Towards minimumk-geodetically connected graphs ⋮ Approximating the minimal sensor selection for supervisory control ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Parameterized complexity of directed spanner problems ⋮ Power optimization for connectivity problems ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Unnamed Item ⋮ Improved approximation algorithms for label cover problems ⋮ Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs ⋮ Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems ⋮ Spanners in sparse graphs ⋮ Complete partitions of graphs ⋮ Improved Approximation for the Directed Spanner Problem ⋮ On Tree-Constrained Matchings and Generalizations ⋮ Combinatorial network abstraction by trees and distances ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ On tree-constrained matchings and generalizations ⋮ Transitive-Closure Spanners: A Survey ⋮ The checkpoint problem ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ The ordered covering problem ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Distance-Preserving Graph Contractions ⋮ A note on the subadditive network design problem ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Distributed Spanner Approximation ⋮ Lasserre integrality gaps for graph spanners and related problems
