On Computing the Gromov Hyperbolicity

DOI10.1145/2780652zbMath1347.68280OpenAlexW1984837166MaRDI QIDQ2828207

Nathann Cohen, David Coudert, Aurélien Lancin

Publication date: 24 October 2016

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01182890/file/CCL15-no-format.pdf

zbMATH Keywords

algorithmsnetworksGromov hyperbolicity

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (18)

The hyperbolicity constant of infinite circulant graphs ⋮ Data center interconnection networks are not hyperbolic ⋮ On Computing the Hyperbolicity of Real-World Graphs ⋮ Cheeger isoperimetric constant of Gromov hyperbolic manifolds and graphs ⋮ On the hyperbolicity of bipartite graphs and intersection graphs ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ Revisiting Decomposition by Clique Separators ⋮ Gromov hyperbolicity in the Cartesian sum of graphs ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Succinct enumeration of distant vertex pairs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ 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
• A survey of the algorithmic aspects of modular decomposition
• Hyperbolicity and chordality of a graph
• Finding the longest isometric cycle in a graph
• Decomposition by clique separators
• An introduction to clique minimal separator decomposition
• Hyperbolic bridged graphs
• Scaled Gromov four-point condition for network graph curvature computation
• Computing the Gromov hyperbolicity of a discrete metric space
• Applying clique-decomposition for computing Gromov hyperbolicity
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Linear Time Split Decomposition Revisited
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• Asymptotic Modularity of Some Graph Classes
• Basic Phylogenetic Combinatorics
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• 1-Hyperbolic Graphs
• Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs
• Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
• Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Transitiv orientierbare Graphen
• Depth-First Search and Linear Graph Algorithms
• On the hyperbolicity of chordal graphs

This page was built for publication: On Computing the Gromov Hyperbolicity