A linear time algorithm for full Steiner trees (Q1068839): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: An Improved Program for the Full Steiner Tree Problem / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the Efficiency of the Algorithm for Steiner Minimal Trees / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3329494 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The Complexity of Computing Steiner Minimal Trees / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Steiner Minimal Trees / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the Problem of Steiner / rank | |||
Normal rank | |||
Latest revision as of 10:04, 17 June 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
