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. (2019) 'When can graph hyperbolicity be computed in linear time?', Algorithmica., 81 (5). pp. 2016-2045.

Abstract

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 number of an n-vertex graph have running time O(n4) . Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2O(k)+O(n+m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential Time Hypothesis (SETH) fails, there is no 2o(k)⋅n2−ε -time algorithm for every ε>0 .

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(523Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/s00453-018-0522-6
Publisher statement:This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-018-0522-6
Date accepted:03 October 2018
Date deposited:24 September 2018
Date of first online publication:13 October 2018
Date first made open access:13 October 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar