A Layout Modification Approach to Via Minimization

Khe Sing The, D. F. Wong, Jingsheng Cong

Research output: Contribution to journalJournal articlepeer-review

11 Citations (Scopus)


We present in this paper a new approach to the via minimization problem. Our approach is to systematically eliminate vias by modifying the routing layout. We have implemented our algorithm and applied it to benchmark routing layouts published in the literature, and obtained significant reduction in the number of vias without increasing the routing area. The experimental results show that our algorithm is more effective in via reduction and more efficient in running time compared to conventional via minimization algorithms. In particular, for Burstein's 19-track two-layer routing solution to Deutsch's difficult problem, our algorithm obtains 34% reduction in the number of vias, which is more than 11% improvement over the conventional constrained via minimization (CVM) approach. The application of our algorithm to various solutions to the Deutsch's difficult problem produces the fewest numbers of vias ever reported in the literature.

Original languageEnglish
Pages (from-to)536-541
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number4
Publication statusPublished - Apr 1991

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this