Computing the Gromov hyperbolicity of a discrete metric space
From MaRDI portal
Publication:2345853
DOI10.1016/J.IPL.2015.02.002zbMATH Open1328.68301arXiv1210.3323OpenAlexW2115857747MaRDI QIDQ2345853FDOQ2345853
Authors: Hervé Fournier, Anas Ismail, Antoine Vigneron 
Publication date: 21 May 2015
Published in: Information Processing Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1210.3323
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
approximation algorithmshyperbolic spacediscrete metric spacealgorithms design and analysis(max, min) matrix product
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Metric spaces, metrizability (54E35)
Cites Work
- Title not available (Why is that?)
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- Embeddings of Gromov hyperbolic spaces
- Recognition of Tree Metrics
- Multiplying matrices faster than coppersmith-winograd
- Title not available (Why is that?)
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
Cited In (26)
- A review of two network curvature measures
- The hyperbolicity constant of infinite circulant 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)
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- On the hyperbolicity constant in graph minors
- When can graph hyperbolicity be computed in linear time?
- Mathematical properties on the hyperbolicity of interval graphs
- Gromov hyperbolicity in Mycielskian graphs
- 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
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
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)
