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]( 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.

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. You can post public domain content. All user-generated content will be freely available online. Please see this page to learn more about Papersγ's terms of use and privacy policy.