Premium
An algorithm for the steiner problem in the euclidean plane
Author(s) -
Winter Pawel
Publication year - 1985
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.3230150305
Subject(s) - steiner tree problem , euclidean geometry , algorithm , computation , network topology , mathematics , plane (geometry) , combinatorics , computer science , geometry , operating system
An algorithm for the exact solution of the Steiner problem in the Euclidean plane is presented. Compared with earlier algorithms, it generates full topologies in a different manner whereby the number of computations is substantially reduced. Furthermore, a large number of full Steiner trees which do not belong to the Steiner minimal tree is identified and discarded by new and efficient tests. The algorithm appears to be considerably faster than any other existing algorithm.