Combinatorial Optimization and Applications

We show that the eccentricities (and thus the centrality indices) of all vertices of a δ-hyperbolic graph G = (V, E) can be computed in linear time with an additive one-sided error of at most cδ, i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimate ê(v) of its eccentricity eccG(v) such that eccG(v) ≤ ê(v) ≤ eccG(v)+cδ for a small constant c. We prove that every δ-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, eccG(v) ≤ eccT (v) ≤ eccG(v)+cδ. We also show that the distance matrix of G with an additive one-sided error of at most c′δ can be computed in O(|V |2 log |V |) time, where c′ < c is a small constant. Recent empirical studies show that many realworld graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity.