Exact computation of Steiner minimal trees in the plane (Q1076029)

From MaRDI portal
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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    SMT
    0 references
    Steiner minimal tree
    0 references
    plane points
    0 references
    algorithms
    0 references
    0 references