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.date.accessioned2007-05-23T09:36:57Z
dc.date.available2007-05-23T09:36:57Z
dc.date.issued1987en_US
dc.identifier.urihttp://hdl.handle.net/1903/4551
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.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1987-42en_US
dc.titleThe Via Minimization Problem is NP-Complete.en_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record