Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00496
Fast approximation of eccentricities and distances in hyperbolic graphs
Victor Chepoi,
Feodor F. Dragan,
Michel Habib,
Yann VaxĂ¨s, and
Hend Alrasheed
Vol. 23, no. 2, pp. 393433, 2019. Regular paper.
Abstract We show that the eccentricities
of all vertices of a $\delta$hyperbolic graph $G=(V,E)$ can be computed in
linear time with an additive onesided error of at most $c\delta$, i.e., after a linear time preprocessing, for every vertex $v$ of $G$ one can compute in $O(1)$ time an estimate $\hat{e}(v)$ of its
eccentricity $ecc_G(v):=\max\{d_G(u,v): u\in V\}$ such that $ecc_G(v)\leq \hat{e}(v)\leq ecc_G(v)+ c\delta$ for a small constant $c$. We prove that every $\delta$hyperbolic graph $G$
has a shortest path tree $T$, constructible in linear time, such that for every vertex $v$ of $G$, $ecc_G(v)\leq ecc_T(v)\leq ecc_G(v)+ c\delta$, where $ecc_T(v):=\max\{d_T(u,v): u\in V\}$. These results are based
on an interesting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertex is to the center of $G$, the smaller its eccentricity is.
We also show that the distance matrix
of $G$ with an additive onesided error of at most $c'\delta$ can be computed in $O(V^2\log^2V)$ 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. So, we analyze the performance of our algorithms for approximating eccentricities and distance matrix on
a number of realworld networks. Our experimental results show that the obtained estimates are even better than the theoretical bounds.

Submitted: October 2018.
Reviewed: March 2019.
Revised: April 2019.
Accepted: May 2019.
Final: May 2019.
Published: June 2019.
Communicated by
Giuseppe Liotta

Journal Supporters
