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

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

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

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

Mathematics of Operations Research

Research output: Working paper

62 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.

Original language	English
Place of Publication	Ithaca, NY
Publisher	ArXiv.org
Number of pages	15
Publication status	Published - 12 Mar 2020

Keywords

k-Hop Steiner tree
Dynamic programming
Network design

Access to Document

ArticleFinal published version, 257 KB

https://arxiv.org/abs/2003.05699

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 proceeding › Conference contribution › Academic › peer-review

Open Access
File
1 Link opens in a new tab Citation (Scopus)

72 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 paper › Preprint › Academic

Open Access
File
47 Downloads (Pure)

Cite this

@techreport{795b66e6289042719ce5005503f8ef3a,

title = "Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics",

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. ",

keywords = "k-Hop Steiner tree, Dynamic programming, Network design",

author = "Martin B{\"o}hm and Ruben Hoeksma and Nicole Megow and Lukas N{\"o}lke and Bertrand Simon",

year = "2020",

month = mar,

day = "12",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics

AU - Böhm, Martin

AU - Hoeksma, Ruben

AU - Megow, Nicole

AU - Nölke, Lukas

AU - Simon, Bertrand

PY - 2020/3/12

Y1 - 2020/3/12

N2 - 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.

AB - 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.

KW - k-Hop Steiner tree

KW - Dynamic programming

KW - Network design

M3 - Working paper

BT - Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics

PB - ArXiv.org

CY - Ithaca, NY

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Research output

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

On Hop-Constrained Steiner Trees in Tree-Like Metrics

Cite this