Title :
The cycle structure of channel graphs in nonsliceable floorplans and a unified algorithm for feasible routing order
Author :
Sur-Kolay, Susmita ; Bhattacharya, Bhargab B.
Author_Institution :
Electron. Unit, Indian Stat. Inst., Calcutta, India
Abstract :
Channel graphs for nonsliceable floorplans are studied for determination of feasible channel routing order. The minimum feedback vertex set (MFVS) formulation is revisited and a polynomial time heuristic is presented. It is shown that feasible routing orders with reserved channels, L-channels, and monotone channels can be obtained from a given MFVS for any floorplan. This approach provides a powerful tool to unify all three previous approaches and produces a solution with comparable efficiency and quality
Keywords :
circuit layout CAD; graph theory; L-channels; channel graphs; channel routing order; cycle structure; feasible routing order; minimum feedback vertex set; monotone channels; nonsliceable floorplans; polynomial time heuristic; unified algorithm; Algorithm design and analysis; Compaction; Feedback; Polynomials; Routing; Topology;
Conference_Titel :
Computer Design: VLSI in Computers and Processors, 1991. ICCD '91. Proceedings, 1991 IEEE International Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-8186-2270-9
DOI :
10.1109/ICCD.1991.139964
