Presentation | 2000/1/11 Heuristic Algorithms for Routing Nonplanar Connections Through Areas under Elements in Printed Wiring Board Design Daisuke Takafuji, Sinpei Sumikawa, Toshimasa Watanabe, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | We propose two algorithms RUE and EJ routing nonplanar connections through areas under elements in printed wiring board design. Nonplanar connections represent jumpers in single-layered design or connection requirements among different layers through vias in multi-layered one. We compare their capability through experiment. Both algorithms repeat finding shortest paths of graphs with congestion costs as edge or vertex weights. It is shown that RUE can embed average 3.8% more nonplanar edges than EJ and that CPU time of RUE is 1 / 6.4 of that of EJ on average. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | printed wiring boards / routing problem / congestion costs / route graphs / shortest paths |
Paper # | VLD99-95,CPSY99-104 |
Date of Issue |
Conference Information | |
Committee | VLD |
---|---|
Conference Date | 2000/1/11(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | VLSI Design Technologies (VLD) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Heuristic Algorithms for Routing Nonplanar Connections Through Areas under Elements in Printed Wiring Board Design |
Sub Title (in English) | |
Keyword(1) | printed wiring boards |
Keyword(2) | routing problem |
Keyword(3) | congestion costs |
Keyword(4) | route graphs |
Keyword(5) | shortest paths |
1st Author's Name | Daisuke Takafuji |
1st Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University() |
2nd Author's Name | Sinpei Sumikawa |
2nd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
3rd Author's Name | Toshimasa Watanabe |
3rd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
Date | 2000/1/11 |
Paper # | VLD99-95,CPSY99-104 |
Volume (vol) | vol.99 |
Number (no) | 529 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |