Premium
Thirty‐five‐point rectilinear steiner minimal trees in a day
Author(s) -
Salowe Jeffrey S.,
Warme David M.
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230250206
Subject(s) - steiner tree problem , combinatorics , terminal (telecommunication) , point (geometry) , mathematics , interconnection , grid , integer (computer science) , tree (set theory) , set (abstract data type) , plane (geometry) , algorithm , computer science , discrete mathematics , geometry , telecommunications , programming language
Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16‐ or 17‐point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer grid.