Previous [1] 2 [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.7 No.3, pp.335-345 (September 1991)
A Branch-and-Bound Algorithm for Single-Row
Routing

Rong-Jaye Chen and Yu-Song Hou
Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan, 30050, R.O.C.

We present a time-efficient algorithm to find an exact solution for the single-row routing problem in this paper. The proposed algorithm is based on the branch-and-bound technique and the interval graphical representation model in [3]. In each stage of the algorithm, an upper bound is obtained by creating a heuristic routing while a lower bound is obtained from the cut numbers in an incomplete graphical interval representation. These bounding values will be computed rapidly by proposed methods. To reduce computing time, we adopt an "outer-track-first" branching strategy and a data tree structure. An `-optimal routing can be obtained if the preset CPU time is exhausted. Computational experience is cited for some generated test problems of up to 50 nets and 150 nodes.

Keywords: single-row routing, interval graphical representation, branch and bound

Received October 15, 1990; revised April 18, 1991.
Communicated by Chin-Chen Chang.

REFERENCES

  1. Kuh, E. S., Kashiwabara, T. and Fujisawa, T., "On Optimum Signle-Row Routing," IEEE Trans. Circuit Syst., Vol. CAS-26, pp.361-368, June 1979.