A linear time algorithm for full Steiner trees (Q1068839)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A linear time algorithm for full Steiner trees |
scientific article; zbMATH DE number 3931036
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for full Steiner trees |
scientific article; zbMATH DE number 3931036 |
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
