著者

本江 俊幸 高橋 篤司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. SLDM, [システムLSI設計技術] (ISSN:09196072)

巻号頁・発行日

vol.2015, no.3, pp.1-6, 2015-05-07

---

次世代リソグラフイ技術の 1 つである側壁プロセスを 2 回用いる SAQP(Self-Aligned Quadruple Patterning) は微細な配線パターンを実現する有望な技術の 1 つであるが,すべての配線パターンを実現できるわけではない.そこで,SAQP で実現可能な配線パターンを生成するために,特殊な 3 色グリッドを用いる配線パターン生成手法が提案されたその生成手法では,配線は SAQP の製造工程に応じて 3 種類に分類される.最終工程に対応する配線は,分岐は許されず,さらに折れ曲がりが禁止されるグリッドが存在する.そのため,最終工程に対応する配線パターンを生成するために,3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる.本稿では,グラフ上に折れ曲がり制約が与えられたとき,一般に,2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す.