The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
Dietmar Cieslik · Optimization · 1991
For a finite set of points in a Minkowski-space a Steiner-Minimal-Tree (SMT) is a shortest tree which interconnects these points. Since the determination of an SMT is unknown or at least NP-hard, we introduce a 1-SMT problem in the way that we allow only one new vertex in the tree. The degrees of vertices in such trees have some restrictions. Consequently, it is possible to solve the 1-SMT problem in polynomial bounded time.