A linear time algorithm for full Steiner trees (Q1068839)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for full Steiner trees |
scientific article |
Statements
A linear time algorithm for full Steiner trees (English)
0 references
1986
0 references
Full Steiner trees are building blocks for the construction of Steiner minimal trees. \textit{Z. A. Melzak} [Can. Math. Bull. 4, 143-148 (1961; Zbl 0101.132)] gave an elegant construction for full Steiner tree. However, no polynomial time implementation of Melzak's construction was previously known. In this paper we show how it can be implemented to run in linear time.
0 references
Full Steiner trees
0 references
Steiner minimal trees
0 references
Melzak's construction
0 references
