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

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 81, No. 5 (2019), p. 2016-2045
Main Author: Fluschnik, Till
Other Involved Persons: Komusiewicz, Christian ; Mertzios, B. ; Nichterlein, André ; Niedermeier, Rolf ; Talmon, Nimrod
Format: electronic Article
Language:English
ISSN:1432-0541
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.
Physical Description:Online-Ressource
DOI:10.1007/s00453-018-0522-6
Subjects:
QR Code: Show QR Code