We analyze several quadratic-time solvable problems, and we show that these problems are
not solvable in truly subquadratic time (that is, in time O (n 2− ϵ) for some ϵ> 0), unless the …

Based on solid theoretical foundations, we present strong evidence that a number of real‐
world networks, taken from different domains (such as Internet measurements, biological …

We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n-
point discrete metric space. We observe that computing the Gromov hyperbolicity from a …

In this work, we analyze the hyperbolicity of real-world networks, a geometric quantity that
measures if a space is negatively curved. We provide two improvements in our …

Graphs are a powerful way to model interactions and relationships in data from a wide
variety of application domains. In this setting, entities represented by vertices at the'center'of …

Through detailed analysis of scores of publicly available data sets corresponding to a wide
range of large-scale networks, from communication and road networks to various forms of …

Through detailed analysis of scores of publicly available data sets corresponding to a wide
range of large-scale networks, from communication and road networks to various forms of …

Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the
one of a tree. This parameter has gained recent attention in the analysis of some graph …

The shortest-path metric d of a connected graph G is 1/2-hyperbolic if and only if it satisfies
d(u,v)+d(x,y)≦\max{d(u,x)+d(v,y),d(u,y)+d(v,x)\}+1, for every 4-tuple u, x, v, y of G. We show …

The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree.
Hence, it is intuitively similar to treewidth, but the measures are formally incomparable …