Computing the Gromov hyperbolicity of a discrete metric space

DOI10.1016/j.ipl.2015.02.002zbMath1328.68301arXiv1210.3323OpenAlexW2115857747MaRDI QIDQ2345853

Antoine Vigneron, Hervé Fournier, Anas Ismail

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

hyperbolic spaceapproximation algorithmsdiscrete metric spacealgorithms design and analysis(max, min) matrix product

Mathematics Subject Classification ID

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

Related Items (24)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Embeddings of Gromov hyperbolic spaces
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• On the Hyperbolicity of Small-World and Treelike Random Graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Recognition of Tree Metrics
• Multiplying matrices faster than coppersmith-winograd

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