\(k\)-Steiner-minimal-trees in metric spaces
type: Item
instance of: scholarly article
title: \(k\)-Steiner-minimal-trees in metric spaces
zbMATH Open document ID: 0935.05033
DOI: 10.1016/S0012-365X(99)00067-9
published in: Discrete Mathematics
publication date: 2000-05-04T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1369775
zbMATH Keywords: metric space
zbMATH Keywords: Steiner-minimal tree
zbMATH Keywords: Steiner tree
zbMATH Keywords: spanning tree problem
zbMATH Keywords: Steiner point
zbMATH Keywords: algorithm
author: Dietmar Cieslik
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00067-9
OpenAlex ID: W1993673146
description: scientific article; zbMATH DE number 1369775