### 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 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 lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.

Original language | English (US) |
---|---|

Title of host publication | 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD |

Pages | 390-395 |

Number of pages | 6 |

DOIs | |

State | Published - Dec 1 2007 |

Event | 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States Duration: Nov 4 2007 → Nov 8 2007 |

### Publication series

Name | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD |
---|---|

ISSN (Print) | 1092-3152 |

### Other

Other | 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD |
---|---|

Country | United States |

City | San Jose, CA |

Period | 11/4/07 → 11/8/07 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Computer Science Applications
- Computer Graphics and Computer-Aided Design

### Cite this

*2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD*(pp. 390-395). [4397296] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2007.4397296