| Presentation | 2015-05-14 NP-completeness of Routing Problem with Bend Constraint Toshiyuki Hongo, Atsushi Takahashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Self-Aligned Quadruple Patterning (SAQP) in which side-wall process is repeated twice is an important manufacturing technique to realize tiny routing pattern in next generation lithography, however, every routing pattern is not realized. In order to obtain SAQP feasible routing patterns, a routing pattern generation method in which a special 3-color grid is used was proposed. In the routing pattern generation method, routing is classified into three according to the manufacturing process of SAQP. Among them, routing corresponding to the last manufacturing process neither allow to branch off nor to bend at several grids. Therefore, an algorithm that obtains a path between two vertices that satisfies bend constraint is required to obtain a routing that corresponds to the last manufacturing process. In this paper, the problem deciding whether there exists a path that satisfies the bend constraint is proved to be NP-complete in general. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Self-Aligned Quadruple Patterning / Bend Constraint / Routing Problem / NP-complete |
| Paper # | VLD2015-3 |
| Date of Issue | 2015-05-07 (VLD) |
| Conference Information | |
| Committee | VLD / IPSJ-SLDM |
|---|---|
| Conference Date | 2015/5/14(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kitakyushu International Conference Center |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | System Design, etc. |
| Chair | Toshiyuki Shibuya(Fujitsu Labs.) / Masahiro Fukui(Ritsumeikan Univ.) |
| Vice Chair | Yusuke Matsunaga(Kyushu Univ.) |
| Secretary | Yusuke Matsunaga(Mitsubishi Electric) / (Ritsumeikan Univ.) |
| Assistant | Takehiro Miyazawa(MMS) / Ryo Yamamoto(Mitsubishi Electric) |
| Paper Information | |
| Registration To | Technical Committee on VLSI Design Technologies / Special Interest Group on System and LSI Design Methodology |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | NP-completeness of Routing Problem with Bend Constraint |
| Sub Title (in English) | |
| Keyword(1) | Self-Aligned Quadruple Patterning |
| Keyword(2) | Bend Constraint |
| Keyword(3) | Routing Problem |
| Keyword(4) | NP-complete |
| 1st Author's Name | Toshiyuki Hongo |
| 1st Author's Affiliation | Toyko Institute of technology(Tokyo Tech) |
| 2nd Author's Name | Atsushi Takahashi |
| 2nd Author's Affiliation | Toyko Institute of technology(Tokyo Tech) |
| Date | 2015-05-14 |
| Paper # | VLD2015-3 |
| Volume (vol) | vol.115 |
| Number (no) | VLD-21 |
| Page | pp.pp.13-18(VLD), |
| #Pages | 6 |
| Date of Issue | 2015-05-07 (VLD) |