Computing Graph Distances Parameterized by Treewidth and Diameter
(2017) 11th International Symposium on Parameterized and Exact Computation In Leibniz International Proceedings in Informatics (LIPIcs) 63. p.1-11- Abstract
- We show that the eccentricity of every vertex in an undirected graph on n vertices can be computed in time n exp O(k*log(d)), where k is the treewidth of the graph and d is the diameter. This means that the diameter and the radius of the graph can be computed in the same time. In particular, if the diameter is constant, it can be determined in time n*exp(O(k)). This result matches a recent hardness result by Abboud, Vassilevska Williams, and Wang [SODA 2016] that shows that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [J. Comp. Syst. Sc., 2001], for any epsilon > 0, no algorithm with running time n^{2-epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/00c4f488-9a55-41de-beca-520c54641a51
- author
- Husfeldt, Thore LU
- organization
- publishing date
- 2017-01-31
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
- series title
- Leibniz International Proceedings in Informatics (LIPIcs)
- volume
- 63
- article number
- 16
- pages
- 11 pages
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 11th International Symposium on Parameterized and Exact Computation
- conference location
- Aarhus, Denmark
- conference dates
- 2016-08-24 - 2016-08-26
- external identifiers
-
- scopus:85014621576
- ISBN
- 978-3-95977-023-1
- DOI
- 10.4230/LIPIcs.IPEC.2016.16
- project
- Algebraic Graph Algorithms
- language
- English
- LU publication?
- yes
- id
- 00c4f488-9a55-41de-beca-520c54641a51
- date added to LUP
- 2017-04-28 11:37:48
- date last changed
- 2022-04-24 23:36:15
@inproceedings{00c4f488-9a55-41de-beca-520c54641a51,
abstract = {{We show that the eccentricity of every vertex in an undirected graph on n vertices can be computed in time n exp O(k*log(d)), where k is the treewidth of the graph and d is the diameter. This means that the diameter and the radius of the graph can be computed in the same time. In particular, if the diameter is constant, it can be determined in time n*exp(O(k)). This result matches a recent hardness result by Abboud, Vassilevska Williams, and Wang [SODA 2016] that shows that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [J. Comp. Syst. Sc., 2001], for any epsilon > 0, no algorithm with running time n^{2-epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.}},
author = {{Husfeldt, Thore}},
booktitle = {{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}},
isbn = {{978-3-95977-023-1}},
language = {{eng}},
month = {{01}},
pages = {{1--11}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
series = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
title = {{Computing Graph Distances Parameterized by Treewidth and Diameter}},
url = {{http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.16}},
doi = {{10.4230/LIPIcs.IPEC.2016.16}},
volume = {{63}},
year = {{2017}},
}