Bubble Sort Approach to Channel Routing
Journal
IEE Proceedings-Computers and Digital Techniques
Journal Volume
147
Journal Issue
6
Pages
415-422
Date Issued
2000
Date
2000
Author(s)
Abstract
An efficient bubble-sort technique for solving the two-layer non-Manhattan channel routing problem is presented. The time and space complexities of our algorithm are O(kn) and O(n), respectively, where k is the number of sorting passes required and n is the total number of two-terminal nets in a routing channel. The algorithm is easily extended to handle the cases with multiterminal nets distributed in a channel. Various tests verify the efficiency of the bubble-sort based router. Experimental results indicate that the router is time-efficient for routing. A three-layer algorithm having O(kn) time based on an identical problem formulation is proposed for solving the non-Manhattan channel routing.
Other Subjects
Algorithms; Communication channels (information theory); Computational complexity; Problem solving; Sorting; Bubble-sort technique; Channel routing; Routers
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
10.pdf
Size
202.7 KB
Format
Adobe PDF
Checksum
(MD5):eac909643906fb6ad1509e71ec50a761