Abstract
The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for highend boards. Existing algorithms for escape routing, an important step in PCB routing, are netcentric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the buscentric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a netcentric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the Longest Common Interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lowerbound for this problem and thus the time complexity of our algorithm is also the best possible.
Original language  English 

Title of host publication  Proceedings of The 2007 IEEE/ACM International Conference on ComputerAided Design, ICCAD 2007 
Publisher  IEEE 
Pages  390395 
Number of pages  6 
ISBN (Print)  9781424413812 
DOIs  
Publication status  Published  4 Nov 2007 
Event  2007 IEEE/ACM International Conference on ComputerAided Design, ICCAD 2007  DoubleTree Hotel, San Jose, United States Duration: 4 Nov 2007 → 8 Nov 2007 https://ieeexplore.ieee.org/xpl/conhome/4397222/proceeding (Conference proceedings) 
Publication series
Name  IEEE/ACM International Conference on ComputerAided Design, Digest of Technical Papers, ICCAD 

ISSN (Print)  10923152 
ISSN (Electronic)  15582434 
Conference
Conference  2007 IEEE/ACM International Conference on ComputerAided Design, ICCAD 2007 

Country/Territory  United States 
City  San Jose 
Period  4/11/07 → 8/11/07 
Internet address 

Scopus Subject Areas
 Software
 Computer Science Applications
 Computer Graphics and ComputerAided Design