Computing the Gromov hyperbolicity of a discrete metric space

Hervé Fournier, Anas Ismail, Antoine E. Vigneron

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We observe that computing the Gromov hyperbolicity from a fixed base-point reduces to a (max,min) matrix product. Hence, using the (max,min) matrix product algorithm by Duan and Pettie, the fixed base-point hyperbolicity can be determined in O(n2.69) time. It follows that the Gromov hyperbolicity can be computed in O(n3.69) time, and a 2-approximation can be found in O(n2.69) time. We also give a (2log2⁡n)-approximation algorithm that runs in O(n2) time, based on a tree-metric embedding by Gromov. We also show that hyperbolicity at a fixed base-point cannot be computed in O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication than currently known.
Original languageEnglish (US)
Pages (from-to)576-579
Number of pages4
JournalInformation Processing Letters
Volume115
Issue number6-8
DOIs
StatePublished - Feb 12 2015

ASJC Scopus subject areas

  • Signal Processing
  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Computing the Gromov hyperbolicity of a discrete metric space'. Together they form a unique fingerprint.

Cite this