scientific article; zbMATH DE number 1424548
The authors present new complexity results on two versions of the planar Steiner tree problem, the bottleneck problem (in which the maximum edge weight is minimized) and the power-\(p\) problem (in which the sum of edge weights raised to the \(p\)-th power is minimized). It is shown that the former problem has no 2-approximation (unless \(P=NP)\) and that the latter is MAX SNP-hard. The interrelation between minimum spanning trees and power-\(p\) Steiner trees is investigated and an approximation algorithm for the bottleneck Steiner tree problem with performance guarantee \(\log_2n\) \((n=\) number of terminals) is developed. For the entire collection see [Zbl 0932.00010].
- Approximations for a bottleneck Steiner tree problem
- On the approximability of the Steiner tree problem
- Optimal and approximate bottleneck Steiner trees
- scientific article; zbMATH DE number 1202981
- scientific article; zbMATH DE number 2044939
- On approximation algorithms for the terminal Steiner tree problem
- Exact algorithms for the bottleneck Steiner tree problem (extended abstract)
- Recent results on approximating the Steiner tree problem and its generalizations
- An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
- Optimal and approximate bottleneck Steiner trees
- The Power of Dynamic Distance Oracles
- Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
- scientific article; zbMATH DE number 1202981 (Why is no real title available?)
- The bottleneck 2-connected k-Steiner network problem for k 2
- An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L_p planes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945797)
