Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
From MaRDI portal
Publication:5089179
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/
Related Items
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
