• DocumentCode
    3710081
  • Title

    A Light Metric Spanner

  • Author

    Lee-Ad Gottlieb

  • Author_Institution
    Dept. of Comput. Sci. &
  • fYear
    2015
  • Firstpage
    759
  • Lastpage
    772
  • Abstract
    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 times the weight of the minimum spanning tree of the set [DHN93]. Whether or not a similar result holds for metric spaces with low doubling dimension has remained an open problem. In this paper, we resolve the question in the affirmative, and show that doubling spaces admit(1 + ε)-stretch spanners with lightness WD = (ddim /ε)O(ddim).
  • Keywords
    "Erbium","Yttrium","Extraterrestrial measurements","Computer science","Buildings","Mathematics"
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/FOCS.2015.52
  • Filename
    7354426
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3710081