文章基本信息

标题：Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
本地全文：下载
作者：Martin B{"o}hm ; Ruben Hoeksma ; Nicole Megow 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：18:1-18:15
DOI：10.4230/LIPIcs.MFCS.2020.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：k-hop Steiner tree; dynamic programming; bounded treewidth