Presentation | 2006-11-21 The Complexity of Three-Dimensional Channel Routing Satoshi TAYU, Shuichi UENO, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The 3-D channel 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 top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | 3-D Channel / bend / net / NP-hard / terminal |
Paper # | CAS2006-61,CST2006-37 |
Date of Issue |
Conference Information | |
Committee | CAS |
---|---|
Conference Date | 2006/11/14(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) | The Complexity of Three-Dimensional Channel Routing |
Sub Title (in English) | |
Keyword(1) | 3-D Channel |
Keyword(2) | bend |
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 | 2006-11-21 |
Paper # | CAS2006-61,CST2006-37 |
Volume (vol) | vol.106 |
Number (no) | 366 |
Page | pp.pp.- |
#Pages | 5 |
Date of Issue |