Computing the Gromov hyperbolicity of a discrete metric space

DOI10.1016/J.IPL.2015.02.002MaRDI QIDQ2345853zbMATH OpenOpenAlexFDO

Authors Hervé Fournier, Anas Ismail, Antoine Vigneron

Publication date 21 May 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.3323

zbMATH Keywords

approximation algorithmshyperbolic spacediscrete metric spacealgorithms design and analysis(max, min) matrix product

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Metric spaces, metrizability (54E35)

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(n^2.69) time. It follows that the Gromov hyperbolicity can be computed in O(n^3.69) time, and a 2-approximation can be found in O(n^2.69) time. We also give a (2 log_2 n)-approximation algorithm that runs in O(n^2) time, based on a tree-metric embedding by Gromov. We also show that hyperbolicity at a fixed base-point cannot be computed in O(n^2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication than currently known.

Recommendations

• Approximation algorithms for the Gromov hyperbolicity of discrete metric spaces
• Fast approximation and exact computation of negative curvature parameters of graphs
• On computing the Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• On computing the hyperbolicity of real-world graphs

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Embeddings of Gromov hyperbolic spaces
• Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
• Multiplying matrices faster than coppersmith-winograd
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Recognition of Tree Metrics
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)

Cited in

(26)

• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• A review of two network curvature measures
• The hyperbolicity constant of infinite circulant graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
• On the hyperbolicity constant in graph minors
• Mathematical properties on the hyperbolicity of interval graphs
• Gromov hyperbolicity in Mycielskian graphs
• When can graph hyperbolicity be computed in linear time?
• Approximation algorithms for the Gromov hyperbolicity of discrete metric spaces
• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• Gromov hyperbolicity in the Cartesian sum of graphs
• On a classical theorem on the diameter and minimum degree of a graph
• On the hyperbolicity constant of circular-arc graphs
• Applying clique-decomposition for computing Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• Results on hyperbolicity in graphs: a survey
• On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
• Metric embedding, hyperbolic space, and social networks
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• On computing the hyperbolicity of real-world graphs
• Fellow travelers phenomenon present in real-world networks
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• On computing the Gromov hyperbolicity

This page was built for publication: Computing the Gromov hyperbolicity of a discrete metric space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345853)