No label defined (Q4945797)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1424548
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1424548 |
Statements
23 March 2000
0 references
power-\(p\) problem
0 references
planar Steiner tree
0 references
bottleneck problem
0 references
0.9410882
0 references
0.92872006
0 references
0.91695815
0 references
0.91662025
0 references
0.9153795
0 references
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].
0 references
