IEEE - Institute of Electrical and Electronics Engineers, Inc. - A Light Metric Spanner

2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

Author(s): Lee-Ad Gottlieb
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 October 2015
Conference Location: Berkeley, CA, USA
Conference Date: 17 October 2015
Page(s): 759 - 772
ISBN (Electronic): 978-1-4673-8191-8
ISSN (Paper): 0272-5428
DOI: 10.1109/FOCS.2015.52
Regular:

It has long been known that d-dimensional Euclidean point sets admit (1+ε)-stretch spanners with lightness WE = ε-O(d), that is the total edge weight is at most WE... View More

Advertisement