Premium
An optimal algorithm for rectilinear steiner trees for channels with obstacles
Author(s) -
Chiang Charles,
Sarrafzadeh Majid,
Wong C. K.
Publication year - 1991
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490190604
Subject(s) - steiner tree problem , channel (broadcasting) , tree (set theory) , mathematics , combinatorics , algorithm , computer science , telecommunications
The channel rectilinear Steiner tree problem is to construct an optimal rectilinear Steiner tree interconnecting n terminals on the upper shore and the lower shore of a channel without crossing any obstacles inside the channel. However, intersecting boundaries of obstacles is allowed. We present an algorithm that computes an optimal channel rectilinear Steiner tree in O(F 1 (k)n + F 2 (k)) time, where k is the number of obstacles inside the channel and F 1 and F 2 are exponential functions of k . For any constant k the proposed algorithm runs in O(n) time.