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

DOI10.4230/LIPIcs.MFCS.2020.18OpenAlexW3080792687MaRDI QIDQ5089179

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

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12687/pdf/LIPIcs-MFCS-2020-18.pdf/

zbMATH Keywords

dynamic programmingbounded treewidth\(k\)-hop Steiner tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem with hop constraints
• Generalized submodular cover problems and applications
• Bounded-hop communication networks
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improved Steiner tree algorithms for bounded treewidth
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Approximating \(k\)-hop minimum-spanning trees
• Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees
• Highway Dimension and Provably Efficient Shortest Path Algorithms
• Using a Hop-Constrained Model to Generate Alternative Communication Network Design
• Greedy Strikes Back: Improved Facility Location Algorithms
• On minimal graphs containing $n$ given points
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Narrow-Shallow-Low-Light Trees with and without Steiner Points
• Vojtěch Jarník's work in combinatorial optimization

This page was built for publication: Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics