Back to Search
Start Over
Parameterized Complexity of Diameter.
- Source :
-
Algorithmica . Feb2023, Vol. 85 Issue 2, p325-351. 27p. - Publication Year :
- 2023
-
Abstract
- Diameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O (n 1.99) -time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC '13), pp 515–524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form f (k) (n + m) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMPUTABLE functions
*APPROXIMATION algorithms
*DIAMETER
*SPARSE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 85
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 161549524
- Full Text :
- https://doi.org/10.1007/s00453-022-01032-9