I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
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(F1(k)n + F2(k)) time, where k is the number of obstacles inside the channel and F1 and F2 are exponential functions of k. For any constant k the proposed algorithm runs in O(n) time. Copyright © 1991 John Wiley & Sons, Ltd.
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Shu Tezuka
WSC 1991