On Computing the Hyperbolicity of Real-World Graphs

DOI10.1007/978-3-662-48350-3_19zbMath1465.68206OpenAlexW1632774644MaRDI QIDQ3452784

David Coudert, Michele Borassi, Andrea Marino, Pierluigi Crescenzi

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01199860/file/BCCM15.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly 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 ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ A simple approach for lower-bounding the distortion in any hyperbolic embedding ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Succinct enumeration of distant vertex pairs ⋮ 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

Cites Work

• Unnamed Item
• Hyperbolicity and chordality of a graph
• 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
• On the Hyperbolicity of Small-World and Treelike Random Graphs
• On Computing the Gromov Hyperbolicity
• Basic Phylogenetic Combinatorics
• Packing and Covering δ-Hyperbolic Spaces by Balls
• The Structure and Function of Complex Networks
• Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
• Non-Hyperbolicity of Random Graphs with Given Expected Degrees

This page was built for publication: On Computing the Hyperbolicity of Real-World Graphs