Show simple item record

The Via Minimization Problem is NP-Complete.

dc.contributor.authorNaclerio, N.J.en_US
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.description.abstractVias between different layers of interconnection on dense integrated circuits tend to reduce yield, degrade performance, and take up a large amount of chip area. Similarly, contact holes on multilayer printed circuit boards add to manufacturing cost, and reduce reliability. Thus, many researchers have examined ways to minimize the number of vias required for a particular circuit layout. In this paper, we analyze the computational complexity of the so-called Constrained Via Minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists. We first prove that the corresponding decision problem is NP-complete. We then show that it remains NP-complete even if one or more of the following restrictions are imposed.en_US
dc.format.extent639754 bytes
dc.relation.ispartofseriesISR; TR 1987-42en_US
dc.titleThe Via Minimization Problem is NP-Complete.en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record