2026-08-10T11:57:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12687 2024-03-06T10:50:34Z ddc:004 open_access

Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics Böhm, Martin Hoeksma, Ruben Megow, Nicole Nölke, Lukas Simon, Bertrand k-hop Steiner tree dynamic programming bounded treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Böhm and Ruben Hoeksma and Nicole Megow and Lukas Nölke and Bertrand Simon 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.18 urn:nbn:de:0030-drops-126870 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.18 eng https://creativecommons.org/licenses/by/3.0/legalcode