The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. Many results on the problem can be found in the literature . The 3-D channel is a 3-D rectilinear grid G consisting of columns,rows,and layers which are rectilinear grid planes defined by fixing x-,y-,and z-coordinates at integers,respectively. The numbers of columns,rows,and layers are called the width,depth,and height of G,respectively. (See Fig.1.)G is called a (W,D,H)-channel if the width is depth is D,and height is H. A vertex of G is a grid point with integer coordinates. We assume without loss of generality that the vertex set of a (W,D,H)-channel is {(x,y,z)|1 ≤ x ≤ W,1≤ y ≤ D,1 ≤ z ≤ H}. A terminal is a vertex of G located in the top or bottom layer. A net is a set of terminals to be connected. The object of the 3-D channel routing problem is to connect the terminals in each net with a tree in G using as few layers as possible in such a way that trees spanning distinct nets are vertex-disjoint. A set of nets is said to be routable in G if G has vertex-disjoint trees spanning the nets.
展开▼
