A Near-Optimal Heuristic Algorithm for Single-Row Routing

L. C. Liu, H. C. Du

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume38
Issue number4
DOIs
StatePublished - Apr 1989

Keywords

  • Heuristic algorithms
  • NP-complete
  • PCB routing
  • single-row routing

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

Cite this