The Via Minimization Problem is NP-Complete.

Simple item page
dc.contributor.authorNaclerio, N.J.en_US
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:36:57Z
dc.date.available2007-05-23T09:36:57Z
dc.date.issued1987en_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.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4551
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

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_87-42.pdf
Size:
624.76 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports