| Article ID: | iaor19911740 |
| Country: | Germany |
| Volume: | 22 |
| Start Page Number: | 291 |
| End Page Number: | 296 |
| Publication Date: | Sep 1991 |
| Journal: | Optimization |
| Authors: | Cieslik D. |
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, is introduced a 1-SMT problem is allowed in the way that only one new vertex is allowed in the tree. The degrees of vertices in such trees have some restrictions. Consequently, it is impossible to solve the 1-SMT problem in polynomial bounded time.