Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner

DOI10.1007/978-3-642-31594-7_25zbMath1272.68153OpenAlexW2568296800MaRDI QIDQ2843256

Michael Dinitz, Ran Raz, Guy Kortsarz

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Lasserre integrality gaps for graph spanners and related problems

This page was built for publication: Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner