Title :
On the Complexity of Three-Dimensional Channel Routing (Extended Abstract)
Author :
Tayu, Satoshi ; Ueno, Shuichi
Author_Institution :
Department of Communications and Integrated Systems, Tokyo Institute of Technology, Tokyo 152-8550-S3-57, Japan
Abstract :
The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable.
Keywords :
Integrated circuit technology; Polynomials; Routing; Three-dimensional integrated circuits; Wires;
Conference_Titel :
Circuits and Systems, 2007. ISCAS 2007. IEEE International Symposium on
Conference_Location :
New Orleans, LA, USA
Print_ISBN :
1-4244-0920-9
Electronic_ISBN :
1-4244-0921-7
DOI :
10.1109/ISCAS.2007.378297
