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.
Original language | English |
---|---|
Title of host publication | 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
Editors | Javier Esparza, Daniel Kráľ |
Place of Publication | Dagstuhl, Germany |
Publisher | Dagstuhl |
Pages | 18:1-18:15 |
ISBN (Print) | 978-3-95977-159-7 |
DOIs | |
Publication status | Published - 18 Aug 2020 |
Event | 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Online event, Prague, Czech Republic Duration: 24 Aug 2020 → 28 Aug 2020 Conference number: 45 http://mfcs.mff.cuni.cz/2020/ |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl--Leibniz-Zentrum für Informatik |
Conference
Conference | 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 |
---|---|
Abbreviated title | MFCS 2020 |
Country/Territory | Czech Republic |
City | Prague |
Period | 24/08/20 → 28/08/20 |
Internet address |