There has been an intensive study on single-row (singlelayer) routing. This problem has been shown to be intractable (NP-complete), and necessary and sufficient conditions for obtaining an optimal realization have been discussed. Many heuristic algorithms have also been proposed in the last couple of years. However, there is only one proposed algorithm based on a sufficient condition of optimality. In this paper, we first obtain a tighter lower bound on the street congestion of optimal realizations. Then a heuristic algorithm based on necessary and sufficient conditions of optimality is proposed. Although it cannot be guaranteed that this algorithm always generates optimal realizations, it indeed generates optimal realiiations for all the 60 test instances with which we experimented. This algorithm is also shown to be time efficient.
Bibliographical noteFunding Information:
Manuscript received June 10, 1986; April 14, 1988, This work was supportd in part by NSF Gran@ ~IP-8605297a nd DCR-840935, and by a grant from The authors are with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 8824550.
- Heuristic algorithms
- PCB routing
- single-row routing