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: Working paper

55 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 nO(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.
Original languageEnglish
Place of PublicationIthaca, NY
PublisherArXiv.org
Number of pages15
Publication statusPublished - 12 Mar 2020

Keywords

  • k-Hop Steiner tree
  • Dynamic programming
  • Network design

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.
  • Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics

    Böhm, M., Hoeksma, R., Megow, N., Nölke, L. & Simon, B., 18 Aug 2020, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Esparza, J. & Kráľ, D. (eds.). Dagstuhl, Germany: Dagstuhl, p. 18:1-18:15 MFCS-2020-18. (Leibniz International Proceedings in Informatics (LIPIcs)).

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

    Open Access
    File
    63 Downloads (Pure)
  • On Hop-Constrained Steiner Trees in Tree-Like Metrics

    Böhm, M., Hoeksma, R., Megow, N., Nölke, L. & Simon, B., 12 Mar 2020, ArXiv.org.

    Research output: Working paperPreprintAcademic

    Open Access
    File
    8 Downloads (Pure)

Cite this