Title :
Channel-Routing Problem in the Knock-Knee Mode Is NP-Complete
Author :
Sarrafzadeh, Majid
Author_Institution :
Department of Electrical Engineering and Computer Science, The Technological Institute, Northwestern University, Evanston, IL, USA
fDate :
7/1/1987 12:00:00 AM
Abstract :
We will show that it is NP-Complete to decide whether an arbitrary instance of the channel-routing problem in the knock-knee mode can be laid out optimally. This result is extended to problems (arising in practice) involving nets of bounded degree
Keywords :
Computer science; Design automation;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.1987.1270298
