Title :
The via minimization problem is NP-complete
Author :
Naclerio, Nicholas J. ; Masuda, Sumio ; Nakajima, Kazuo
Author_Institution :
Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA
fDate :
11/1/1989 12:00:00 AM
Abstract :
The authors analyze the computational complexity of the 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 using only two layers. The authors first prove that the corresponding decision problem is NP-complete. They then show that it remains NP-complete even if one or more of the following restrictions are imposed: (1) the input layout must conform to a rectangular grid; (2) vias are restricted to lie at junctions which existed in the input layout; and (3) the maximum junction degree is limited to six or more
Keywords :
circuit layout CAD; computational complexity; minimisation of switching nets; NP-complete; computational complexity; constrained via minimization; input layout; minimum cardinality set; rectangular grid; valid layer assignment; Computer architecture; Computer network reliability; Computer networks; Fault tolerance; Fault tolerant systems; Joining processes; Multiprocessing systems; Multiprocessor interconnection networks; Parallel processing; Transient analysis;
Journal_Title :
Computers, IEEE Transactions on
