TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1996

COGA 5-Wheel

Page Content

to Navigation

Preprints 1996

Switchbox Routing in VLSI Design: Closing the Complexity Gap
Citation key Report-500-1996
Author Stephan Hartmann and Markus W. Schäffter and Andreas S. Schulz
Year 1996
Number 500
Note appeared WG'96
Institution Technische Universität Berlin, Institut für Mathematik
Abstract The design of integrated circuits has achieved a great deal of attention in the last decade. In the routing phase, there have survived two open layout problems which are important from both the theoretical and the practical point of view. Up to now, switchbox routing has been known to be solvable in polynomial time when there are only 2–terminal nets, and to be \textrmNP–complete in case there exist nets involving at least five terminals. Our main result is that this problem is \textrmNP–complete even if no net has more that three terminals. Hence, from the theoretical perspective, the \SRP is completely settled. The \textrmNP–completeness proof is based on a reduction from a special kind of the satisfiability problem. It is also possible to adopt our construction to channel routing which shows that this problem is \textrmNP–complete, even if each net does not consist of more than five terminals. This improves upon a result of Sarrafzadeh who showed the \textrmNP–completeness in case of nets with no more than six terminals.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe