T. Fluschnik
When can graph hyperbolicity be computed in linear time?
Fluschnik, T.; Komusiewicz, C.; Mertzios, G.B.; Nichterlein, A.; Niedermeier, R.; Talmon, N.
Authors
C. Komusiewicz
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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. (2023, July). When can graph hyperbolicity be computed in linear time?. Presented at Algorithms and Data Structures Symposium (WADS) 2017, St. John’s, NL, Canada
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | Algorithms and Data Structures Symposium (WADS) 2017 |
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 |
Print ISSN | 0302-9743 |
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
Accepted Conference Proceeding
(339 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-319-62127-2_34.
You might also like
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Equitable scheduling on a single machine
(2021)
Presentation / Conference Contribution
Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search