Skip to main content

Research Repository

Advanced Search

When can graph hyperbolicity be computed in linear time?

Fluschnik, T.; Komusiewicz, C.; Mertzios, G.B.; Nichterlein, A.; Niedermeier, R.; Talmon, N.

When can graph hyperbolicity be computed in linear time? Thumbnail


Authors

T. Fluschnik

C. Komusiewicz

A. Nichterlein

R. Niedermeier

N. Talmon



Contributors

Faith Ellen
Editor

Antonina Kolokolova
Editor

Jörg-Rüdiger Sack
Editor

Abstract

Hyperbolicity measures, in terms of (distance) metrics, 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 practical algorithms for computing the hyperbolicity number of a n-vertex graph have running time O(n4)O(n4) . Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time 2O(k)+O(n+m)2O(k)+O(n+m) (m being the number of graph edges, k being the size of a vertex cover) while at the same time, unless the SETH fails, there is no 2o(k)n22o(k)n2 -time algorithm.

Citation

Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2017). When can graph hyperbolicity be computed in linear time?. In F. Ellen, A. Kolokolova, & J. Sack (Eds.), Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings (397-408). https://doi.org/10.1007/978-3-319-62127-2_34

Conference Name Algorithms and Data Structures Symposium (WADS) 2017
Conference Location St. John’s, NL, Canada
Start Date Jul 31, 2023
End Date Aug 2, 2017
Acceptance Date Apr 14, 2017
Online Publication Date Jul 5, 2017
Publication Date Jul 5, 2017
Deposit Date Jun 26, 2017
Publicly Available Date Jul 5, 2018
Pages 397-408
Series Title Lecture notes in computer science
Series Number 10389
Series ISSN 0302-9743,1611-3349
Book Title Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings.
ISBN 9783319621265
DOI https://doi.org/10.1007/978-3-319-62127-2_34
Public URL https://durham-repository.worktribe.com/output/1146963

Files





You might also like



Downloadable Citations