License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.18
URN: urn:nbn:de:0030-drops-126870
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12687/
Go to the corresponding LIPIcs Volume Portal

Böhm, Martin ; Hoeksma, Ruben ; Megow, Nicole ; Nölke, Lukas ; Simon, Bertrand

Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics

pdf-format:
LIPIcs-MFCS-2020-18.pdf (0.6 MB)

Abstract

We consider the problem of computing a Steiner tree of minimum cost under a k-hop constraint which requires the depth of the tree to be at most k. Our main result is an exact algorithm for metrics induced by graphs of bounded treewidth that runs in time n^O(k). For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if k is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the k-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension.

BibTeX - Entry

@InProceedings{bhm_et_al:LIPIcs:2020:12687,
  author =	{Martin B{\"o}hm and Ruben Hoeksma and Nicole Megow and Lukas N{\"o}lke and Bertrand Simon},
  title =	{{Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12687},
  URN =		{urn:nbn:de:0030-drops-126870},
  doi =		{10.4230/LIPIcs.MFCS.2020.18},
  annote =	{Keywords: k-hop Steiner tree, dynamic programming, bounded treewidth}
}

Keywords: k-hop Steiner tree, dynamic programming, bounded treewidth
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI