\(k\)-Steiner-minimal-trees in metric spaces (Q1808781): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(99)00067-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1993673146 / rank | |||
Normal rank |
Latest revision as of 09:53, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(k\)-Steiner-minimal-trees in metric spaces |
scientific article |
Statements
\(k\)-Steiner-minimal-trees in metric spaces (English)
0 references
4 May 2000
0 references
For a given set \(N\) of points in a metric space, a Steiner-minimal tree (SMT) is a tree, connecting the points of \(N\) with minimum total length. A \(k\)-SMT is a Steiner tree, but now at most \(k\)-additional `Steiner' points (points on the tree with degree at least three that do not belong to \(N\)) may be added. The problem to find a 0-SMT is the classic shortest spanning tree problem and can be solved in linear time. On the other hand, the unrestricted Steiner tree problem is NP-hard. This paper considers the complexity of the \(k\)-Steiner tree problem, where \(k\) is a given integer (considered to be fixed). It shows that if two conditions are fulfilled, then the problem is polynomial time solvable. The first of these conditions is that there is a natural number \(c\) that only depends on the metric space, such that any Steiner point in any \(k\)-SMT has vertex degree at most \(c\), and the second condition states that for each number \(n\) between 3 and \(kc- k+1\) there is an algorithm that finds the shortest tree for each set of \(n\) points. Also, it is shown that the relative defect going from a \((k-1)\)-SMT to a \(k\)-SMT tends to zero, when \(k\) goes to infinity.
0 references
metric space
0 references
Steiner-minimal tree
0 references
Steiner tree
0 references
spanning tree problem
0 references
Steiner point
0 references
algorithm
0 references