Strong Inapproximability of the Basic k-Spanner Problem
- 1 January 2000
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 636-648
- https://doi.org/10.1007/3-540-45022-x_54
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- The Hardness of Approximating Spanner ProblemsLecture Notes in Computer Science, 2000
- Distributed Computing: A Locality-Sensitive ApproachPublished by Society for Industrial & Applied Mathematics (SIAM) ,2000
- On the hardness of approximating spannersPublished by Springer Nature ,1998
- A parallel repetition theoremPublished by Association for Computing Machinery (ACM) ,1995
- Generating Sparse 2-SpannersJournal of Algorithms, 1994
- On sparse spanners of weighted graphsDiscrete & Computational Geometry, 1993
- New sparseness results on graph spannersPublished by Association for Computing Machinery (ACM) ,1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Graph spannersJournal of Graph Theory, 1989
- Graph TheoryPublished by Springer Nature ,1979