DocumentCode
1169338
Title
Two NP-hard interchangeable terminal problems
Author
Sahni, Sartaj ; Wu, San-yuan
Author_Institution
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
Volume
7
Issue
4
fYear
1988
fDate
4/1/1988 12:00:00 AM
Firstpage
467
Lastpage
472
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;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/43.3181
Filename
3181
Link To Document