Absolute Area Approximation in Channel Routing is NP-Hard

Rajat Kumar Pal


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 \emph{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 \emph{VH} routing model remain NP-hard even in the three-layer \emph{HVH} routing model.


Absolute approximation; Area minimization; Channel routing problem; NP-hardness; Doglegging, Reserved layer model; Manhattan routing

Full Text:


DOI: http://dx.doi.org/10.26713%2Fjims.v1i2+%26+3.16

eISSN 0975-5748; pISSN 0974-875X