Fast approximation of centrality and distances in hyperbolic graphs

Victor Chepoi, Feodor F. Dragan, Michel Habib +2

We show that the eccentricities (and thus the centrality indices) of all vertices of a $\delta$-hyperbolic graph $G=(V,E)$ can be computed in linear time with an additive one-sided erro…