| Presentation | 2010-11-18 On the Complexity of Three-Dimensional Orthogonal Face Routing Satoshi TAYU, Shuichi UENO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The 3-D switchbox routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the faces of the 3-D channel. A net is a set of terminals to be connected. The objective of the 3-D switchbox routing problem is to connect the terminals in each net with a Steiner tree (wire) in G in such a way that wires for distinct nets are disjoint. The 3-D orthogonal face routing is a special case of the 3-D switchbox routing such that every terminal is located on a pair of orthogonal faces. This paper shows that the 3-D orthogonal face routing is intractable even though every net has terminals both on the orthogonal faces. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | 3-D channel / face / net / NP-hard / terminal |
| Paper # | CAS2010-68,CST2010-41 |
| Date of Issue |
| Conference Information | |
| Committee | CAS |
|---|---|
| Conference Date | 2010/11/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 | Circuits and Systems (CAS) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Complexity of Three-Dimensional Orthogonal Face Routing |
| Sub Title (in English) | |
| Keyword(1) | 3-D channel |
| Keyword(2) | face |
| Keyword(3) | net |
| Keyword(4) | NP-hard |
| Keyword(5) | terminal |
| 1st Author's Name | Satoshi TAYU |
| 1st Author's Affiliation | Department of Communications and Integrated Systems Tokyo Institute of Technology() |
| 2nd Author's Name | Shuichi UENO |
| 2nd Author's Affiliation | Department of Communications and Integrated Systems Tokyo Institute of Technology |
| Date | 2010-11-18 |
| Paper # | CAS2010-68,CST2010-41 |
| Volume (vol) | vol.110 |
| Number (no) | 283 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |