Title :
The automation design based on graphs for the symmetrical routing in integrated circuit
Author_Institution :
Center for Discrete Math. & Theor. Comput. Sci., Fuzhou Univ., Fuzhou, China
Abstract :
Channel routing is a key problem in the area of VLSI layout. Finding a minimum width solution of channel routing was proved to be NP-hard by Szymanski. In this paper, we come to a conclusion that the minimum parallel clique cover of $CCG$ is equivalent to the optimal solution of 2-layer manhattan channel routing where vertical constrains are noncyclic and extra empty columns and doglegs are not allowed. We also gave a new heuristic algorithm based on the conclusion to solve the problem of 2-layer manhattan channel routing.
Keywords :
VLSI; computational complexity; graph theory; integrated circuit layout; network routing; 2-layer manhattan channel routing; NP-hard problem; VLSI layout; automation design; channel routing; graph theory; heuristic algorithm; integrated circuit; symmetrical routing; Routing; Channel routing; Graph; Manhattan model; VLSI;
Conference_Titel :
System Science, Engineering Design and Manufacturing Informatization (ICSEM), 2011 International Conference on
Conference_Location :
Guiyang
Print_ISBN :
978-1-4577-0247-1
DOI :
10.1109/ICSSEM.2011.6081312
