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: | |
| Look up in GoogleScholar |
