Exact computation of Steiner minimal trees in the plane (Q1076029): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(86)90062-1 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2029791926 / rank | |||
Normal rank | |||
Revision as of 23:33, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exact computation of Steiner minimal trees in the plane |
scientific article |
Statements
Exact computation of Steiner minimal trees in the plane (English)
0 references
1986
0 references
A Steiner minimal tree for a given set \(A=\{a_ 1,...,a_ n\}\) of plane points is a tree which interconnects these points and whose total length is minimum. The tree may contain other vertices of the plain besides \(a_ 1,...,a_ n\). Several algorithms are known for construction of Steiner minimal trees but all of them are of exponential complexity. The present paper further improves the Winter's approach in such a way that all 17-point problems and most of 30-point problems can be solved in a reasonable time.
0 references
SMT
0 references
Steiner minimal tree
0 references
plane points
0 references
algorithms
0 references
