(untitled) (Journal of Informatics and Mathematical Sciences, 2009)
The computational complexity of minimizing area of routing in two-and three-layer channels is known to be NP-hard [9,13]. In this paper we establish the result of computing an absolute approximate solution for no-dogleg two-layer VH channel routing is NP-hard. This result holds for channels with only two-terminal nets, where we impose a restriction of a partition of nets, such that the nets of the same class in the partition are to be assigned to the same track in any routing solution. We have proved the NP-hardness of the absolute area approximation problem for channels with nets having a bounded number of terminals per net. The later results have also been extended for routing using restricted doglegging. All the problems considered above for the two-layer VH routing model remain NP-hard even in the three-layer HVH routing model.