On Hop-Constrained Steiner Trees in Tree-Like Metrics
From MaRDI portal
Publication:5864216
DOI10.1137/21M1425487OpenAlexW4281669277MaRDI QIDQ5864216
Ruben Hoeksma, Nicole Megow, Lukas Nölke, Martin Böhm, Bertrand Simon
Publication date: 3 June 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.05699
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Distance in graphs (05C12)
Cites Work
- 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
- 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
- VC-Dimension and Shortest Path Algorithms
- Proof verification and the hardness of approximation problems
- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- Fourier meets M\"{o}bius: fast subset convolution
- Bypassing the embedding
- 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
- On the History of the Minimum Spanning Tree Problem
- Reducibility among Combinatorial Problems
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Parameterized Algorithms
- The steiner problem in graphs
- 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
- A tight bound on approximating arbitrary metrics by tree metrics
- Vojtěch Jarník's work in combinatorial optimization
- Tree embeddings for hop-constrained network design
This page was built for publication: On Hop-Constrained Steiner Trees in Tree-Like Metrics
