Computing the gromov hyperbolicity of a discrete metric space

H. Fournier, A. Ismail, A. Vigneron
Information Processing Letters, 115(6-8), 576-579, (2015)

Computing the gromov hyperbolicity of a discrete metric space


Algorithms design and analysis, Approximation algorithms,Discrete metric space, Hyperbolic space, (max,min) matrix product


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)O(n2.69) time. It follows that the Gromov hyperbolicity can be computed in O(n3.69)O(n3.69) time, and a 2-approximation can be found in O(n2.69)O(n2.69) time. We also give a (2log2⁡n)(2log2⁡n)-approximation algorithm that runs in O(n2)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)O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication than currently known.


DOI: 10.1016/j.ipl.2015.02.002


Website PDF

See all publications 2015