Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CHANNEL ROUTING:
Reports tagged with channel routing:
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