A Near-Optimal Heuristic Algorithm for Single-Row Routing

L. C. Liu, H. C. Du

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)603-608
Number of pages6
JournalIEEE Transactions on Computers
Issue number4
StatePublished - Apr 1989

Bibliographical note

Funding 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
  • NP-complete
  • PCB routing
  • single-row routing


Dive into the research topics of 'A Near-Optimal Heuristic Algorithm for Single-Row Routing'. Together they form a unique fingerprint.

Cite this