David Coudert
Salle 24-25/405
The Gromov hyperbolicity is an important parameter for analyzing complex networks since it is a measure of the tree-likeness of a graph from a metric perspective. This notion has been recently applied in different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. For instance, it gives bounds on the best possible stretch of some greedy-routing schemes in Internet-like graphs. The best known algorithm for computing hyperbolicity has running-time O(n^{3.69}), which is clearly prohibitive for big graphs. In this talk, we will present recent advances on the computation of this parameter. We will present an algorithm that performs well in practice. Although its time complexity is in O(n^4), it can compute the hyperbolicity of graphs with 100.000 nodes in short time. We will discuss the limitations of this algorithm and related open problems. We will also provide some results on the time complexity lower bound. In addition, we will show how to use some simple properties of the graph to get tight bounds on its hyperbolicity, e.g., being bipartite, a line graph, vertex transitive, etc. These properties are used for establishing bounds on the hyperbolicity of various interconnection network topologies proposed for large data centers.