On computing the Gromov hyperbolicity
From MaRDI portal
Publication:2828207
DOI10.1145/2780652zbMATH Open1347.68280OpenAlexW1984837166MaRDI QIDQ2828207FDOQ2828207
Authors: 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
Recommendations
- On computing the hyperbolicity of real-world graphs
- Fast approximation and exact computation of negative curvature parameters of graphs
- Fast approximation and exact computation of negative curvature parameters of graphs
- Computing the Gromov hyperbolicity of a discrete metric space
- When can graph hyperbolicity be computed in linear time?
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12)
Cites Work
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Decomposition by clique separators
- Basic phylogenetic combinatorics.
- Transitiv orientierbare Graphen
- Hyperbolic bridged graphs
- Notes on diameters, centers, and approximating trees of \(\delta\)-hyperbolic geodesic spaces and graphs
- Hyperbolicity and chordality of a graph
- On the hyperbolicity of chordal graphs
- A Combinatorial Decomposition Theory
- Linear time split decomposition revisited
- Decomposition of Directed Graphs
- Recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs
- 1-Hyperbolic Graphs
- Fast computation of empirically tight bounds for the diameter of massive graphs
- A survey of the algorithmic aspects of modular decomposition
- Asymptotic modularity of some graph classes
- Computing the Gromov hyperbolicity of a discrete metric space
- An introduction to clique minimal separator decomposition
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Lack of Gromov-hyperbolicity in colored random networks
- Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
- Scaled Gromov four-point condition for network graph curvature computation
- Approximation algorithms for the Gromov hyperbolicity of discrete metric spaces
- Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
- Finding the longest isometric cycle in a graph
- Applying clique-decomposition for computing Gromov hyperbolicity
Cited In (28)
- Core-periphery models for graphs based on their \( \delta \)-hyperbolicity: an example using biological networks
- The hyperbolicity constant of infinite circulant graphs
- Fast approximation and exact computation of negative curvature parameters of graphs
- Computing the Gromov hyperbolicity of a discrete metric space
- When can graph hyperbolicity be computed in linear time?
- 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
- Title not available (Why is that?)
- Gromov hyperbolicity in the Cartesian sum of graphs
- Leanness computation: small values and special graph classes
- Data center interconnection networks are not hyperbolic
- Cheeger isoperimetric constant of Gromov hyperbolic manifolds and graphs
- Revisiting decomposition by clique separators
- Into the square: on the complexity of some quadratic-time solvable problems
- 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
- Computing the Gysin Map Using Fixed Points
- Fast approximation of eccentricities and distances in hyperbolic graphs
- On computing the hyperbolicity of real-world graphs
- Succinct enumeration of distant vertex pairs
- Fellow travelers phenomenon present in real-world networks
- Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
- Computing graph hyperbolicity using dominating sets
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
This page was built for publication: On computing the Gromov hyperbolicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828207)
