{"updated":"2025-01-20T19:17:03.821393+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00141653","sets":["1164:2036:7856:8244"]},"path":["8244"],"owner":"11","recid":"141653","title":["折れ曲がり制約を含む配線問題のNP完全性"],"pubdate":{"attribute_name":"公開日","attribute_value":"2015-05-07"},"_buckets":{"deposit":"c557a5c7-ae0f-4be4-8698-fe4f23a3b74e"},"_deposit":{"id":"141653","pid":{"type":"depid","value":"141653","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"折れ曲がり制約を含む配線問題のNP完全性","author_link":["207474","207477","207476","207475"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"折れ曲がり制約を含む配線問題のNP完全性"},{"subitem_title":"NP-completeness of Routing Problem with Bend Constraint","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"レイアウト・テスト","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2015-05-07","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京工業大学大学院理工学研究科通信情報工学専攻"},{"subitem_text_value":"東京工業大学大学院理工学研究科通信情報工学専攻"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Communications and Computer Engineering, Tokyo Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"Department of Communications and Computer Engineering, Tokyo Institute of Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/141653/files/IPSJ-SLDM15171003.pdf"},"date":[{"dateType":"Available","dateValue":"2100-01-01"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-SLDM15171003.pdf","filesize":[{"value":"1.3 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"10"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"9979ba01-1969-4764-b9ab-c3728ed532ba","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2015 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"本江, 俊幸"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"高橋, 篤司"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Toshiyuki, Hongo","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Atsushi, Takahashi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11451459","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8639","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"次世代リソグラフイ技術の 1 つである側壁プロセスを 2 回用いる SAQP(Self-Aligned Quadruple Patterning) は微細な配線パターンを実現する有望な技術の 1 つであるが，すべての配線パターンを実現できるわけではない．そこで，SAQP で実現可能な配線パターンを生成するために，特殊な 3 色グリッドを用いる配線パターン生成手法が提案されたその生成手法では，配線は SAQＰ の製造工程に応じて 3 種類に分類される．最終工程に対応する配線は，分岐は許されず，さらに折れ曲がりが禁止されるグリッドが存在する．そのため，最終工程に対応する配線パターンを生成するために，3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる．本稿では，グラフ上に折れ曲がり制約が与えられたとき，一般に，2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"研究報告システムとLSIの設計技術（SLDM）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2015-05-07","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"2015-SLDM-171"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-19T00:19:12.470467+00:00","id":141653,"links":{}}