On the hardness of approximating spanners
- 1 January 1998
- book chapter
- Published by Springer Nature
- p. 135-146
- https://doi.org/10.1007/bfb0053970
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- Generating Sparse 2-SpannersJournal of Algorithms, 1994
- Grid spannersNetworks, 1993
- On sparse spanners of weighted graphsDiscrete & Computational Geometry, 1993
- New sparseness results on graph spannersPublished by Association for Computing Machinery (ACM) ,1992
- A Fast Parametric Maximum Flow Algorithm and ApplicationsSIAM Journal on Computing, 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
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- Approximation algorithms for combinatorial problemsJournal of Computer and System Sciences, 1974
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952