The Via Minimization Problem is NP-Complete.

Loading...
Thumbnail Image

Files

TR_87-42.pdf (624.76 KB)
No. of downloads: 499

Publication or External Link

Date

1987

Advisor

Citation

DRUM DOI

Abstract

Vias 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.

Notes

Rights