ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > KNOCK KNEE:
Reports tagged with knock knee:
TR01-076 | 24th October 2001
Robert Albin Legenstein

On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

In this article we consider a basic problem in the layout of VLSI-circuits, the channel-routing problem in the knock-knee mode. We show that knock-knee channel routing with 3-terminal nets is NP-complete and thereby settling a problem that was open for more than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>



ISSN 1433-8092 | Imprint