Comments:

Some "abstract" real-world graphs (such as social networks, WWW networks, call graphs, scientific collaboration graphs; and not road networks or power grid networks) empirically seem to have a small [hyperbolicity](https://en.wikipedia.org/wiki/Hyperbolic_metric_space). This property can be used to approximate the input graph by a tree. The tree can, in turn, be used to approximate efficiently some quantities such as the distance between two nodes. "The key point here is that in a hyperbolic graph selecting the root in the hyperbolic core ensures that it is already at the intersection of O(N) shortest paths" Question: How can I select a root node efficiently? Question: Is there any guaranty on the obtained approximation? Question: How can I compute the hyperbolicity of a graph efficiently? Not sure why there is "dynamic" in the title.

Please consider to register or login to comment on the paper.