Constrained via minimization for three-layer routing

K. E. Chang*, H. F. Jyu, W. S. Feng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


The constrained via minimization problem for VLSI three-layer 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. This problem has been shown to be NP-complete15. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.

Original languageEnglish
Pages (from-to)346-354
Number of pages9
JournalComputer-Aided Design
Issue number6
Publication statusPublished - 1989
Externally publishedYes


  • VLSI design
  • computer-aided design
  • graph contractibility
  • layer assignment
  • via minimization

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Constrained via minimization for three-layer routing'. Together they form a unique fingerprint.

Cite this