Computing Graph Distances Parameterized by Treewidth and Diameter

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikation11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
FörlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sidor1–11
Antal sidor11
Volym63
ISBN (elektroniskt)978-3-95977-023-1
StatusPublished - 2017 jan 31
PublikationskategoriForskning
Peer review utfördJa
EvenemangThe 11th International Symposium on Parameterized and Exact Computation - Aarhus, Danmark
Varaktighet: 2016 aug 242016 aug 26
Konferensnummer: 11
http://conferences.au.dk/algo16/ipec/

Publikationsserier

NamnLeibniz International Proceedings in Informatics (LIPIcs)
FörlagSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volym63

Konferens

KonferensThe 11th International Symposium on Parameterized and Exact Computation
Förkortad titelIPEC
LandDanmark
OrtAarhus
Period2016/08/242016/08/26
Internetadress

Related projects

Visa alla (1)