Title :
The module orientation problem based on Manhattan wire measure is still NP-complete [VLSI design]
Author :
Yan, Jin-Tai ; Hsiao, Pei-Yung
Author_Institution :
Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan
Abstract :
In this paper, Manhattan measure of distance is used to estimate the length of routing nets, and the module orientation problem based on Manhattan measure is proposed. According to the geometrical properties of Manhattan measure, the module orientation problem for the macro cell placement and the standard cell placement can be reducible to the minimum cut partition problem in an undirected graph and further proven to be NP-complete
Keywords :
VLSI; computational complexity; graph theory; integrated circuit layout; network routing; IC layout; Manhattan wire measure; NP-complete; VLSI design; geometrical properties; macro cell placement; minimum cut partition problem; module orientation problem; routing nets; standard cell placement; undirected graph; Area measurement; Circuits; Length measurement; Phase measurement; Pins; Position measurement; Routing; Semiconductor device measurement; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 1993., Proceedings of the 36th Midwest Symposium on
Conference_Location :
Detroit, MI
Print_ISBN :
0-7803-1760-2
DOI :
10.1109/MWSCAS.1993.343004
