Premium
Reductions for the rectilinear steiner tree problem
Author(s) -
Winter Pawel
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.3230260404
Subject(s) - steiner tree problem , mathematics , combinatorics , metric (unit) , terminal (telecommunication) , tree (set theory) , grid , simple (philosophy) , network planning and design , computer science , discrete mathematics , algorithm , geometry , telecommunications , philosophy , operations management , epistemology , economics
The rectilinear Steiner tree problem asks for a shortest network connecting n terminals in the rectilinear plane (with L 1 ‐metric). The problem can be considered as a special case of the Steiner tree problem in a grid network obtained by drawing horizontal and vertical lines through terminals. The reductions developed for the network variant of the Steiner tree problem can therefore also be used in the rectilinear case. However, computational experience indicates that they are not very powerful in the rectilinear grids. We introduce a limited number of rectilinear reductions based on the geometrical properties of terminals. Experimental results show that these reductions are extremely powerful while being quite simple to verify and easy to implement. For randomly generated problem instances with one terminal per row and column, The number of nonterminals remaining seems to be around 20‐‐25% of their original number. Furthermore, The performance of geometrical reductions improves as the density of terminals in fixed‐size grids grows.