Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing

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

doi:10.1109/43.277633

Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing

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

Department of Electrical Engineering & Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	603-609
Number of pages	7
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	13
Issue number	5
DOIs	https://doi.org/10.1109/43.277633
State	Published - May 1994

ASJC Scopus subject areas

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

Access to Document

10.1109/43.277633

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

@article{ae54092cfa174ad4850b52e17403450b,

title = "Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing",

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.",

author = "{Roger Chen}, {C. Y.} and Uminder Singh and Hou, {Cliff Yungchin}",

year = "1994",

month = may,

doi = "10.1109/43.277633",

language = "English (US)",

volume = "13",

pages = "603--609",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing

AU - Roger Chen, C. Y.

AU - Singh, Uminder

AU - Hou, Cliff Yungchin

PY - 1994/5

Y1 - 1994/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028428934&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028428934&partnerID=8YFLogxK

U2 - 10.1109/43.277633

DO - 10.1109/43.277633

M3 - Article

AN - SCOPUS:0028428934

VL - 13

SP - 603

EP - 609

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 5

ER -