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

DOI10.4230/LIPICS.MFCS.2020.18OpenAlexW3080792687MaRDI QIDQ5089179FDOQ5089179

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)

Cites Work

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

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)