Hyperbolicity [P15]

The (Gromov) hyperbolicity is a topological property of a graph, which has been recently applied in several different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. Computing the hyperbolicity of a graph can be very time consuming: indeed, the best available algorithm has running-time O(n3.69), which is clearly prohibitive for big graphs. We provide a new and more efficient algorithm: although its worst-case complexity is O(n4), in practice it is much faster, allowing, for the first time, the computation of the hyperbolicity of graphs with up to 200,000 nodes. You can get the source code used in our experiments, written in ANSI C, as a single zip archive, and more than 60 real-world graphs, also in a single zip archive.