Heuristic Algorithms for Single Row Routing

A heuristic algorithm, based on the criterion of having nets with larger cut numbers assigned to inner tracks and nets with smaller cut numbers assigned to outer tracks, for single row routing problem has recently been proposed by Tarng et al. It has been reported that this algorithm has always been able to produce the optimal solutions for all the examples tested so far. In this paper, we have proved that algorithms based on the heuristic criterion of cut numbers produce optimal solutions for instances in which all nets cover at least one common node (i.e., form a single group). However, the algorithm proposed by Tarng et al. may not produce optimal solutions for instances of multiple net groups. Thus, several possible heuristic algorithms based on the same criterion, but also taking into consideration the net grouping situation have been proposed. The experimental results show that the proposed algorithms are faster and often generate better results than the one proposed by Tarng et al. A tighter lower bound on the number of tracks required is also obtained in this paper.