標題: An improved optimal algorithm for bubble-sorting-based non-Manhattan channel routing
作者: Yan, JT
交大名義發表
National Chiao Tung University
關鍵字: bubble sorting;channel routing;optimal algorithm;physical design
公開日期: 1-Feb-1999
摘要: It is well known that a non-Manhattan channel router always uses fewer routing tracks than a Manhattan router in a channel, To our knowledge, for a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chaudhary's O(kn(2)) heuristic algorithm [8] and Chen's O(k(2)n) optimal algorithm [9] have been, respectively, proposed, where n is the number of terminals and k is the number of routing tracks in a channel. However, the time complexity of the two algorithms is in O(n(3)) time in the worst case. In this paper, based on optimality-oriented swap-direction selection in an optimal bubble-sorting solution, an improved optimal algorithm for a BSNMCR problem is proposed, and the time complexity of the proposed algorithm is proven to be in O(kn) time and in O(n(2)) time in the worst case.
URI: http://dx.doi.org/10.1109/43.743726
http://hdl.handle.net/11536/31560
ISSN: 0278-0070
DOI: 10.1109/43.743726
期刊: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Volume: 18
Issue: 2
起始頁: 163
結束頁: 171
Appears in Collections:Articles


Files in This Item:

  1. 000078407000007.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.