Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

When can graph hyperbolicity be computed in linear time?

Fluschnik, T. and Komusiewicz, C. and Mertzios, G.B. and Nichterlein, A. and Niedermeier, R. and Talmon, N. (2017) 'When can graph hyperbolicity be computed in linear time?', in Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings. Cham: Springer, pp. 397-408. Lecture notes in computer science. (10389).

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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(331Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-319-62127-2_34
Publisher statement:The final publication is available at Springer via https://doi.org/10.1007/978-3-319-62127-2_34.
Date accepted:14 April 2017
Date deposited:28 June 2017
Date of first online publication:05 July 2017
Date first made open access:05 July 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar