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

DOI10.1145/2818375zbMath1398.68392arXiv1203.0224OpenAlexW1725039148MaRDI QIDQ4962219

Michael Dinitz, Ran Raz, Guy Kortsarz

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.0224

zbMATH Keywords

graph spannersprobabilistically checkable proofs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Distributed Spanner Approximation ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming

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