The Hardness of Approximating Spanner Problems
- 24 March 2000
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 370-381
- https://doi.org/10.1007/3-540-46541-3_31
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- On the hardness of approximating spannersPublished by Springer Nature ,1998
- Generating Sparse 2-SpannersJournal of Algorithms, 1994
- Grid spannersNetworks, 1993
- New sparseness results on graph spannersPublished by Association for Computing Machinery (ACM) ,1992
- Generating sparse spanners for weighted graphsLecture Notes in Computer Science, 1990
- Graph spannersJournal of Graph Theory, 1989
- There are planar graphs almost as good as the complete graphs and as short as minimum spanning treesLecture Notes in Computer Science, 1989
- Which triangulations approximate the complete graph?Lecture Notes in Computer Science, 1989
- Delaunay graphs are almost as good as complete graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- There is a planar graph almost as good as the complete graphPublished by Association for Computing Machinery (ACM) ,1986