Graph contractability problem for VLSI layer assignment
作者:
Kuo‐En Chang,
Horng‐Fei Jyu,
Wu‐Shuing Feng,
期刊:
Journal of the Chinese Institute of Engineers
(Taylor Available online 1989)
卷期:
Volume 12,
issue 4
页码: 485-495
ISSN:0253-3839
年代: 1989
DOI:10.1080/02533839.1989.9677185
出版商: Taylor & Francis Group
关键词: NP‐complete;layer assisgnment;graph contractability;crossing graph
数据来源: Taylor
摘要:
The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we transform the problem of layer assignment for three‐layer routing to the contractability problem of 3‐colorable graph. This problem is shown to be NP‐complete and a heuristic algorithm is proposed on the basis of the graph contractability model. From our experimental results, the algorithm is faster and efficient to generate very good results. In the average, the number of vias can be reduced by 30 percent or so.
点击下载:
PDF (823KB)
返 回