Name
Abstract | ||
|---|---|---|
The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. 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 bus-centric 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 net-centric 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 lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.
|
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/ICCAD.2007.4397296 | ICCAD |
Keywords | Field | DocType |
lcis problem,different bus,network routing,time complexity,optimal bus sequencing,tree searching,balanced search tree data structure,pcb routing problem,circuit optimisation,chosen bus,optimal bus,escape routing,dense pcbs,longest common interval sequence problem,printed circuits,circuit complexity,bus-centric escape,pcb routing,new optimization problem,bus-centric escape routing problem,net-centric escape router,net-centric routing,dynamic programming,n log n,data structure,lower bound,scheduling,optimization problem | Data structure,Dynamic programming,Static routing,Computer science,Destination-Sequenced Distance Vector routing,Real-time computing,Router,Time complexity,Optimization problem,Search tree | Conference |
ISSN | ISBN | Citations |
1092-3152 E-ISBN : 978-1-4244-1382-9 | 978-1-4244-1382-9 | 10 |
PageRank | References | Authors |
1.04 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hui Kong | 1 | 77 | 5.50 |
| Tan Yan | 2 | 295 | 24.12 |
| Martin D. F. Wong | 3 | 3525 | 363.70 |
| Muhammet Mustafa Ozdal | 4 | 313 | 23.18 |