A linear time algorithm for full Steiner trees (Q1068839): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q224543 |
Changed an Item |
||
| Property / author | |||
| Property / author: Frank K. Hwang / rank | |||
Normal rank | |||
Revision as of 20:34, 11 February 2024
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
