@techreport{oai:ipsj.ixsq.nii.ac.jp:00141653,
 author = {本江, 俊幸 and 高橋, 篤司 and Toshiyuki, Hongo and Atsushi, Takahashi},
 issue = {3},
 month = {May},
 note = {次世代リソグラフイ技術の 1 つである側壁プロセスを 2 回用いる SAQP(Self-Aligned Quadruple Patterning) は微細な配線パターンを実現する有望な技術の 1 つであるが，すべての配線パターンを実現できるわけではない．そこで，SAQP で実現可能な配線パターンを生成するために，特殊な 3 色グリッドを用いる配線パターン生成手法が提案されたその生成手法では，配線は SAQＰ の製造工程に応じて 3 種類に分類される．最終工程に対応する配線は，分岐は許されず，さらに折れ曲がりが禁止されるグリッドが存在する．そのため，最終工程に対応する配線パターンを生成するために，3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる．本稿では，グラフ上に折れ曲がり制約が与えられたとき，一般に，2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す．, 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.},
 title = {折れ曲がり制約を含む配線問題のNP完全性},
 year = {2015}
}