Title :
Two NP-hard interchangeable terminal problems
Author :
Sahni, Sartaj ; Wu, San-yuan
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
fDate :
4/1/1988 12:00:00 AM
Abstract :
Two subproblems that arise when routing channels with interchangeable terminals are shown to be NP-hard. These problems are: (1) determining whether there is a net-to-terminal assignment that results in an acyclic vertical and constraint graph and (2) for instances with acyclic vertical constraint graphs, obtaining net-to-terminal assignments for which the length of the longest path in the vertical constraint graph is minimum
Keywords :
cellular arrays; circuit layout CAD; integrated logic circuits; NP-hard interchangeable terminal problems; PLA routing; cellular arrays; complexity; instances with acyclic vertical constraint graphs; longest path; net-to-terminal assignment; routing channels with interchangeable terminals; subproblems; Computer science; Design automation; Helium; NP-complete problem; Programmable logic arrays; Programmable logic devices; Routing;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
