折れ曲がり制約を含む配線問題のNP完全性

• 本江 俊幸

  東京工業大学大学院理工学研究科通信情報工学専攻

• 高橋 篤司

  東京工業大学大学院理工学研究科通信情報工学専攻

書誌事項

タイトル別名

• NP-completeness of Routing Problem with Bend Constraint

抄録

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

収録刊行物

• 情報処理学会研究報告. SLDM, [システムLSI設計技術]

  情報処理学会研究報告. SLDM, [システムLSI設計技術] 2015 (3), 1-6, 2015-05-07

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

キーワード

• レイアウト・テスト

詳細情報

• CRID: 1574231877578550912
• NII論文ID: 110009893644
• NII書誌ID: AA11451459
• ISSN: 09196072
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles
  • KAKEN