A preprocessor for the via minimization problem

K. C. Chang, H. C. Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


The objective of the via minimization is to assign wire segments into different layers to minimize the number of vias required. Several algorithms have been proposed for the Constrained Via Minimization (CVM) problem where the topology of the given layout is fixed. In a CVM problem, some vias may be "essential" to the given layout. That is, they have to be selected and cannot be replaced by other vias. In this paper we present a procedure to find most of the essential vias. This procedure can be used as a preprocessor for the algorithms for CVM problems. Experimental results show that the procedure is efficient and can identify most of essential vias.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd ACM/IEEE Design Automation Conference, DAC 1986
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)0818607025
StatePublished - Jul 2 1986
Event23rd ACM/IEEE Design Automation Conference, DAC 1986 - Las Vegas, United States
Duration: Jun 29 1986Jul 2 1986

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other23rd ACM/IEEE Design Automation Conference, DAC 1986
CountryUnited States
CityLas Vegas

Bibliographical note

Funding Information:
*This work was supported in part by NSF Grant DCR-8405498, by a grant from CDC/IIoneywell/Sperry, and by a grant from MEIS.

Fingerprint Dive into the research topics of 'A preprocessor for the via minimization problem'. Together they form a unique fingerprint.

Cite this