Computing the gromov-hausdorff distance for metric trees

Conference Paper

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O(min{n, rn})-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O(n)-approximation algorithm. 1

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Kyle, FOX; Nath, A; Sidiropoulos, A; Wang, Y

Published Date

  • June 1, 2018

Published In

Volume / Issue

  • 14 / 2

Electronic International Standard Serial Number (EISSN)

  • 1549-6333

International Standard Serial Number (ISSN)

  • 1549-6325

Digital Object Identifier (DOI)

  • 10.1145/3185466

Citation Source

  • Scopus