Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Dr George Mertzios

Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R. & Talmon, N. (2017), When can graph hyperbolicity be computed in linear time?, in Ellen, Faith, Kolokolova, Antonina & Sack, Jörg-Rüdiger eds, Lecture Notes in Computer Science, volume 10389 Algorithms and Data Structures Symposium (WADS). St. John’s, NL, Springer, Cham, 397-408.

Author(s) from Durham

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.