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

DOI10.4230/LIPICS.MFCS.2020.18MaRDI QIDQ5089179zbMATH OpenOpenAlexFDO

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

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)

Cites work

• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 5070513 (Why is no real title available?)
• scientific article; zbMATH DE number 6472583 (Why is no real title available?)
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• Approximating \(k\)-hop minimum-spanning trees
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Bounded-hop communication networks
• Generalized submodular cover problems and applications
• Greedy Strikes Back: Improved Facility Location Algorithms
• Highway dimension and provably efficient shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Improved Steiner tree algorithms for bounded 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
• Network design problems with bounded distances via shallow-light Steiner trees
• On formulations and methods for the hop-constrained minimum spanning tree problem
• On minimal graphs containing $n$ given points
• Parameterized algorithms
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem with hop constraints
• Using a Hop-Constrained Model to Generate Alternative Communication Network Design
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Vojtěch Jarník's work in combinatorial optimization

Cited in

(2)

• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089179)