Graph contractability problem for vlsi layer assignment

Kuo En Chang; Horng Fei Jyu; Wu Shuing Feng

doi:10.1080/02533839.1989.9677185

Graph contractability problem for vlsi layer assignment

Kuo En Chang^*, Horng Fei Jyu, Wu Shuing Feng

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	485-495
Number of pages	11
Journal	Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume	12
Issue number	4
DOIs	https://doi.org/10.1080/02533839.1989.9677185
Publication status	Published - 1989 Jun

Keywords

Crossing graph
Graph contractability
Layer assisgnment
NP-complete

ASJC Scopus subject areas

General Engineering

Access to Document

10.1080/02533839.1989.9677185

Cite this

@article{83063bfb37c24d979b25b19260a6df9c,

title = "Graph contractability problem for vlsi layer assignment",

abstract = "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.",

keywords = "Crossing graph, Graph contractability, Layer assisgnment, NP-complete",

author = "Chang, {Kuo En} and Jyu, {Horng Fei} and Feng, {Wu Shuing}",

year = "1989",

month = jun,

doi = "10.1080/02533839.1989.9677185",

language = "English",

volume = "12",

pages = "485--495",

journal = "Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an",

issn = "0253-3839",

publisher = "Chinese Institute of Engineers",

number = "4",

}

TY - JOUR

T1 - Graph contractability problem for vlsi layer assignment

AU - Chang, Kuo En

AU - Jyu, Horng Fei

AU - Feng, Wu Shuing

PY - 1989/6

Y1 - 1989/6

N2 - 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.

AB - 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.

KW - Crossing graph

KW - Graph contractability

KW - Layer assisgnment

KW - NP-complete

UR - http://www.scopus.com/inward/record.url?scp=0024700828&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024700828&partnerID=8YFLogxK

U2 - 10.1080/02533839.1989.9677185

DO - 10.1080/02533839.1989.9677185

M3 - Article

AN - SCOPUS:0024700828

SN - 0253-3839

VL - 12

SP - 485

EP - 495

JO - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

JF - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

IS - 4

ER -

Graph contractability problem for vlsi layer assignment

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this