Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing

C. Y. Roger Chen, Uminder Singh, Cliff Yungchin Hou

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

It has been pointed out that, in many cases, results generated by non-Manhattan channel routers will be better than those generated by Manhattan routers. Non-optimal bubble sort based algorithms for non-Manhattan channel routing have been proposed in the literature by also allowing connections in the +45° and 45° directions. In this paper, optimal algorithms are proposed for the two-layer and three-layer non-Manhattan channel routing problems based on an identical problem formulation. The time complexities of our algorithms and the existing algorithm (which produces the best results so far) are O(K2 N) and O(K N2), respectively, where N is the number of terminals (i.e., the length) of the channel and K is the number of routing tracks (i.e., the height) in the channel. K is always less than N, and in most cases is much smaller than N. Clearly, a significant improvement in time complexity over the existing algorithm (which produces the best results so far) is achieved, while ensuring optimality.

Original languageEnglish (US)
Pages (from-to)603-609
Number of pages7
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume13
Issue number5
DOIs
StatePublished - May 1994

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing'. Together they form a unique fingerprint.

  • Cite this