Hierarchical bubble-sorting-based non-Manhattan channel routing

For a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chen's O(k(2)n) optimal algorithm and Yan's O(kn) optimal algorithm have be en proposed respectively where n is the number of terminals and k is the nu mber of routing tracks in a channel. For the sorting process of a given vec tor, these two optimal algorithms consider that a left-swap pass or a right -swap pass is an overall pass. As the distribution of most of the routing n ets in a channel has a local property a vector may be divided into several smaller subvectors, and each subvector can be sorted by a left-swap pass or a right-swap pass to further optimise the number of tracks in a channel. I n the paper, based on an optimality-oriented swap-direction selection and a 'divide-and-conquer' technology, a hierarchical BSNMCR (HBSNMCR) problem i s formulated and an O(hn) optimal algorithm is proposed, where h is the num ber of routing tracks in a HBSNMCR solution, for h less than or equal to k.