Aarhus University Seal

Covering metric spaces by few trees

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Yair Bartal, Hebrew University of Jerusalem
  • ,
  • Ora Nova Fandina
  • Ofer Neiman, Ben-Gurion University of the Negev

A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y∈X has a low distortion path in one of the trees. If it has the stronger property that every point x∈X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.

Original languageEnglish
JournalJournal of Computer and System Sciences
Pages (from-to)26-42
Number of pages17
Publication statusPublished - Dec 2022

Bibliographical note

Publisher Copyright:
© 2022 Elsevier Inc.

    Research areas

  • Metric embedding, Spanners, Tree covers

See relations at Aarhus University Citationformats

ID: 276976767