Item type |
SIG Technical Reports(1) |
公開日 |
2020-10-09 |
タイトル |
|
|
タイトル |
イジングモデルによる有向グラフに対する誘導部分グラフ同型問題の解法 |
言語 |
|
|
言語 |
jpn |
資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
著者所属 |
|
|
|
早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻 |
著者所属 |
|
|
|
早稲田大学グリーン・コンピューティング・システム研究機構 |
著者所属 |
|
|
|
早稲田大学グリーン・コンピューティング・システム研究機構 |
著者所属 |
|
|
|
NTTソフトウェアイノベーションセンタ |
著者所属 |
|
|
|
NTTソフトウェアイノベーションセンタ |
著者所属 |
|
|
|
NTTソフトウェアイノベーションセンタ |
著者所属 |
|
|
|
早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻 |
著者所属(英) |
|
|
|
en |
|
|
Dept. Computer Science and Communications Engineering, Waseda University |
著者所属(英) |
|
|
|
en |
|
|
Green Computing System Research Organization, Waseda University |
著者所属(英) |
|
|
|
en |
|
|
Green Computing System Research Organization, Waseda University |
著者所属(英) |
|
|
|
en |
|
|
NTT Software Innovation Center |
著者所属(英) |
|
|
|
en |
|
|
NTT Software Innovation Center |
著者所属(英) |
|
|
|
en |
|
|
NTT Software Innovation Center |
著者所属(英) |
|
|
|
en |
|
|
Dept. Computer Science and Communications Engineering, Waseda University |
著者名 |
吉村, 夏一
多和田, 雅師
田中, 宗
新井, 淳也
巴, 徳瑪
八木, 哲志
戸川, 望
|
論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
近年,組合せ最適化問題の準最適解を高速に得られるハードウェアとして,イジングマシンが注目されている.イジングマシンはイジングモデルのみを入力として受け付けるため,組合せ最適化問題ごとにイジングモデルへのマッピングを考える必要がある.組合せ最適化問題として誘導部分グラフ同型問題に注目する.ネットワークや木,系列などの構造を持つ多くの現実問題はその構造を頂点集合と辺集合からなるグラフで表すことができる.誘導部分グラフ同型問題は対象となるグラフ構造の中に特定の構造を持つ誘導部分グラフが存在するか否かを判定する問題であり,集積回路から不正回路を探索する際などに出現する.現実問題をグラフ構造に落とし込む際,無向グラフでは表現できず有向グラフが必要な場合もある.本稿では,有向グラフに対する誘導部分グラフ同型問題をイジングマシンによって解く手法を提案する.提案手法ではイジングモデルのエネルギー関数として,一方の有向グラフが他方の有向グラフに対して,誘導部分グラフ同型となるときイジングモデルのエネルギーが最小となるよう定式化する.提案手法により有向グラフに対する誘導部分グラフ同型問題を実際にイジングモデル上で求解した結果を報告する. |
書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA12894105 |
書誌情報 |
研究報告量子ソフトウェア(QS)
巻 2020-QS-1,
号 25,
p. 1-7,
発行日 2020-10-09
|
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2435-6492 |
Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |