Previous | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | [ 7 ] | [ 8 ] | [ 9 ] | [ 10 ] | [ 11 ] |

¡@

**T. K. Yu ^{+} and D. T. Lee^{*+}**

National Taiwan University

Taipei, 106 Taiwan

E-mail: tkyu@ntu.edu.tw

Academia Sinica

Taipei, 115 Taiwan

E-mail: dtlee@iis.sinica.edu.tw

VLSI layout design is typically decomposed into four steps: placement, global routing, routing region definition and ordering, and detailed routing. The crossing distribution problem occurs prior to detailed routing, in which crossings of nets are distributed according to design constraints. In this paper, we propose an
*O*(*n*log *n*) time algorithm for the crossing distribution problem for two-terminal nets in two regions, where n is the number of nets. This algorithm improves a previously known result that runs in
*O*(*n*^{2}) time [6]. We also give an *O*(*n*^{2}) time algorithm for the crossing distribution problem for three-terminal nets under some assumption.

*
Keywords:
*
VLSI, crossing distribution problem, crossing minimization problem, detailed routing, two-terminal net, multi-terminal net

Retrieve PDF document (**200401_01.pdf**)

Received January 31, 2003; accepted July 4, 2003.

Communicated by Shiuh-Pyng Shieh
^{*}A preliminary version of this paper has been presented at the 2002 International Computer Symposium, 2002.