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

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

doi:10.4230/LIPIcs.MFCS.2020.18

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: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 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 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	https://doi.org/10.4230/LIPIcs.MFCS.2020.18
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	http://mfcs.mff.cuni.cz/2020/

Access to Document

10.4230/LIPIcs.MFCS.2020.18Licence: CC BY

LIPIcs-MFCS-2020-18Final published version, 571 KBLicence: CC BY

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). [MFCS-2020-18] (Leibniz International Proceedings in Informatics (LIPIcs)). Dagstuhl. https://doi.org/10.4230/LIPIcs.MFCS.2020.18

Böhm, Martin ; Hoeksma, Ruben ; Megow, Nicole ; Nölke, Lukas ; Simon, Bertrand. / Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). editor / Javier Esparza ; Daniel Kráľ. Dagstuhl, Germany : Dagstuhl, 2020. pp. 18:1-18:15 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{c96eab9f82104387b0509fbf7e840bee,

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

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

year = "2020",

month = aug,

day = "18",

doi = "10.4230/LIPIcs.MFCS.2020.18",

language = "English",

isbn = "978-3-95977-159-7",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Dagstuhl",

pages = "18:1--18:15",

editor = "Javier Esparza and Daniel Kr{\'a}{\v I}",

booktitle = "45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)",

address = "Germany",

note = "45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, MFCS 2020 ; Conference date: 24-08-2020 Through 28-08-2020",

url = "http://mfcs.mff.cuni.cz/2020/",

}

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)., MFCS-2020-18, Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Dagstuhl, Germany, pp. 18:1-18:15, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Czech Republic, 24/08/20. https://doi.org/10.4230/LIPIcs.MFCS.2020.18

Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics. / Böhm, Martin; Hoeksma, Ruben; Megow, Nicole; Nölke, Lukas; Simon, Bertrand.

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). ed. / Javier Esparza; Daniel Kráľ. Dagstuhl, Germany : Dagstuhl, 2020. 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

TY - GEN

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

N1 - Conference code: 45

PY - 2020/8/18

Y1 - 2020/8/18

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

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

U2 - 10.4230/LIPIcs.MFCS.2020.18

DO - 10.4230/LIPIcs.MFCS.2020.18

M3 - Conference contribution

SN - 978-3-95977-159-7

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 18:1-18:15

BT - 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

A2 - Esparza, Javier

A2 - Kráľ, Daniel

PB - Dagstuhl

CY - Dagstuhl, Germany

T2 - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

Y2 - 24 August 2020 through 28 August 2020

ER -

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

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this