When Can Graph Hyperbolicity be Computed in Linear Time?
Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms used in practice for computing the hyperbolicity numb...
|Published in:||Algorithmica : an international journal in computer science, Vol. 81, No. 5 (2019), p. 2016-2045|
|Other Involved Persons:||; ; ; ;|
|Item Description:||This work was initiated at the yearly research retreat of the Algorithmics and Computational Complexity (AKT) group of TU Berlin, held in Krölpa, Thuringia, Germany, from April 3rd till April 9th, 2016. An extended abstract appeared in the Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS ’17), volume 10389, pages 397–408. Springer, 2017. This version contains additional details and full proofs.|
|QR Code:||Show QR Code|
Algorithmica : an international journal in computer science, Vol. 81, No. 5 (2019), p. 2016-2045