On computing the hyperbolicity of real-world graphs

DOI10.1007/978-3-662-48350-3_19MaRDI QIDQ3452784zbMATH OpenOpenAlexFDO

Authors Michele Borassi, David Coudert, Pilu Crescenzi, Andrea Marino

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

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

Recommendations

• On computing the Gromov hyperbolicity
• When can graph hyperbolicity be computed in linear time?
• When can graph hyperbolicity be computed in linear time?
• Fast approximation and exact computation of negative curvature parameters of graphs
• Fast approximation and exact computation of negative curvature parameters of graphs

Cites work

• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Applying clique-decomposition for computing Gromov hyperbolicity
• Basic phylogenetic combinatorics.
• Complex networks. Structure, robustness and function.
• Computing the Gromov hyperbolicity of a discrete metric space
• Hyperbolicity and chordality of a graph
• Non-hyperbolicity of random graphs with given expected degrees
• Notes on diameters, centers, and approximating trees of -hyperbolic geodesic spaces and graphs
• On computing the Gromov hyperbolicity
• Packing and Covering δ-Hyperbolic Spaces by Balls
• The Structure and Function of Complex Networks

Cited in

(27)

• A simple approach for lower-bounding the distortion in any hyperbolic embedding
• Fellow travelers phenomenon present in real-world networks
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Fast approximation of centrality and distances in hyperbolic graphs
• Computing the Gromov hyperbolicity of a discrete metric space
• Applying clique-decomposition for computing Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• On computing the Gromov hyperbolicity
• Data center interconnection networks are not hyperbolic
• On the hyperbolicity of bipartite graphs and intersection graphs
• Hyperbolic random graphs: separators and treewidth
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Efficient shortest paths in scale-free networks with underlying hyperbolic geometry
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• Fast approximation and exact computation of negative curvature parameters of graphs
• Succinct enumeration of distant vertex pairs
• When can graph hyperbolicity be computed in linear time?
• When can graph hyperbolicity be computed in linear time?
• Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
• Computing graph hyperbolicity using dominating sets
• Core-periphery models for graphs based on their \( \delta \)-hyperbolicity: an example using biological networks
• Leanness computation: small values and special graph classes
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Additive approximation algorithm for geodesic centers in -hyperbolic graphs
• Discrete-time gradient flows in Gromov hyperbolic spaces
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

This page was built for publication: On computing the hyperbolicity of real-world graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452784)