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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

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 languageEnglish
Title of host publication45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
EditorsJavier Esparza, Daniel Kráľ
Place of PublicationDagstuhl, Germany
PublisherDagstuhl
Pages18:1-18:15
ISBN (Print)978-3-95977-159-7
DOIs
Publication statusPublished - 2020
Event45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Online event, Prague, Czech Republic
Duration: 24 Aug 202028 Aug 2020
Conference number: 45
http://mfcs.mff.cuni.cz/2020/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik

Conference

Conference45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
Abbreviated titleMFCS 2020
CountryCzech Republic
CityPrague
Period24/08/2028/08/20
Internet address

Fingerprint Dive into the research topics of 'Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics'. Together they form a unique fingerprint.

  • Cite this

    Böhm, M., Hoeksma, R., Megow, N., Nölke, L., & Simon, B. (2020). Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics. In J. Esparza, & D. Kráľ (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (pp. 18:1-18:15). (Leibniz International Proceedings in Informatics (LIPIcs)). Dagstuhl, Germany: Dagstuhl. https://doi.org/10.4230/LIPIcs.MFCS.2020.18