Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-076 | 24th October 2001 00:00

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

RSS-Feed




TR01-076
Authors: Robert Albin Legenstein
Publication: 12th November 2001 17:59
Downloads: 3595
Keywords: 


Abstract:

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 channel
routing with 5-terminal nets is NP-complete.
Furthermore, it is known that this problem is solvable in polynomial
time if only 2-terminal nets are involved (This problem was
addressed for example by Frank in 1982 and by Formann, D. Wagner,
and F. Wagner in 1993).



ISSN 1433-8092 | Imprint