| 講演名 | 2019-11-14 イジングモデルによる類似誘導部分グラフ同型問題の解法 吉村 夏一(早大), 多和田 雅師(早大), 田中 宗(早大), 新井 淳也(NTT), 巴 徳瑪(NTT), 八木 哲志(NTT), 内山 寛之(NTT), 戸川 望(早大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | イジングマシンを用いて組合せ最適化問題の準最適解を高速に得るためには，組合せ最適化問題からイジングモデルへのマッピングを考える必要がある．本研究では組合せ最適化問題のひとつである誘導部分グラフ同型問題に注目する．誘導部分グラフ同型問題は対象となるグラフ構造の中に特定の構造を持つ部分グラフが存在するか否かを判定する問題であり，集積回路から不正回路を探索する際や化学物質中における特定の化学結合パタンを探索する際など多くの現実問題に出現する．特にそれらの現実問題では厳密には特定のグラフ構造を持たないとき，近い構造を有する不正回路や化学結合パタンを探索したいという需要が存在する．本稿では，誘導部分グラフ同型問題をイジングマシンによって類似的に解く手法を提案する．グラフ構造の類似性の尺度としてグラフ辺編集距離を定義する．厳密に誘導部分グラフ同型性が成り立つときはグラフ辺編集距離が$0$であるとし，誘導部分グラフ同型性が成り立たないときはグラフ辺編集距離をもとに定量的に近いグラフを探索する．提案手法ではイジングモデルのエネルギー関数として，一方のグラフが他方のグラフに対して，最も近しい誘導部分グラフとなるときイジングモデルのエネルギーが最小となるよう定式化する．定式化されたイジングモデルにより，定義したグラフ辺編集距離のもと誘導部分グラフ同型に最も近いグラフを探索することを可能にする．提案手法により類似誘導部分グラフ同型問題を実際にイジングモデル上で求解した結果を報告する． |
| 抄録(英) | |
| キーワード(和) | 類似誘導部分グラフ同型問題 / 誘導部分グラフ同型問題 / イジングマシン / イジングモデル / 組合せ最適化問題 |
| キーワード(英) | |
| 資料番号 | VLD2019-41,DC2019-65 |
| 発行日 | 2019-11-06 (VLD, DC) |
| 研究会情報 | |
| 研究会 | VLD / DC / CPSY / RECONF / ICD / IE / IPSJ-SLDM / IPSJ-EMB / IPSJ-ARC |
|---|---|
| 開催期間 | 2019/11/13(から3日開催) |
| 開催地（和） | 愛媛県男女共同参画センター |
| 開催地（英） | Ehime Prefecture Gender Equality Center |
| テーマ（和） | デザインガイア2019 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2019 -New Field of VLSI Design- |
| 委員長氏名（和） | 戸川 望(早大) / 福本 聡(首都大東京) / 入江 英嗣(東大) / 柴田 裕一郎(長崎大) / 永田 真(神戸大) / 木全 英明(NTT) / 田宮 豊(富士通研) / / 井上 弘士(九大) |
| 委員長氏名（英） | Nozomu Togawa(Waseda Univ.) / Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Yuichiro Shibata(Nagasaki Univ.) / Makoto Nagata(Kobe Univ.) / Hideaki Kimata(NTT) / Yutaka Tamiya(Fujitsu Lab.) / / Hiroshi Inoue(Kyushu Univ.) |
| 副委員長氏名（和） | 福田 大輔(富士通研) / 高橋 寛(愛媛大) / 鯉渕 道紘(NII) / 中島 耕太(富士通研) / 佐野 健太郎(理研) / 山口 佳樹(筑波大) / 高橋 真史(東芝メモリ) / 児玉 和也(NII) / 高橋 桂太(名大) |
| 副委員長氏名（英） | Daisuke Fukuda(Fujitsu Labs.) / Hiroshi Takahashi(Ehime Univ.) / Michihiro Koibuchi(NII) / Kota Nakajima(Fujitsu Lab.) / Kentaro Sano(RIKEN) / Yoshiki Yamaguchi(Tsukuba Univ.) / Masafumi Takahashi(Toshiba-memory) / Kazuya Kodama(NII) / Keita Takahashi(Nagoya Univ.) |
| 幹事氏名（和） | 小平 行秀(会津大) / 桜井 祐市(日立) / 新井 雅之(日大) / 難波 一輝(千葉大) / 津邑 公暁(名工大) / 高前田 伸也(北大) / 谷川 一哉(広島市大) / 三好 健文(イーツリーズ・ジャパン) / 夏井 雅典(東北大) / 柘植 政利(ソシオネクスト) / 早瀬 和也(NTT) / 松尾 康孝(NHK) / 土谷 亮(滋賀県大) / 岩崎 裕江(NTT) / 佐々木 通(三菱電機) / / 近藤 正章(東大) / 塩谷 亮太(名大) / 田中 美帆(富士通研) / 長谷川 揚平(東芝メモリ) |
| 幹事氏名（英） | Yukihide Kohira(Univ. of Aizu) / Yuichi Sakurai(Hitachi) / Masayuki Arai(Nihon Univ.) / Kazuteru Namba(Chiba Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Shinya Takameda(Hokkaido Univ.) / Kazuya Tanigawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan) / Masanori Natsui(Tohoku Univ.) / Masatoshi Tsuge(Socionext) / Kazuya Hayase(NTT) / Yasutaka Matsuo(NHK) / Akira Tsuchiya(Univ. Shiga Prefecture) / Hiroe Iwasaki(NTT) / Toru Sasaki(Mitsubishi Electric) / / Masaaki Kondo(Univ. of Tokyo) / Ryota Shioya(Nagoya Univ.) / Miho Tanaka(Fujitsu Labs.) / Yohei Hasegawa(Toshiba Memory) |
| 幹事補佐氏名（和） | 池田 一樹(日立) / / 有間 英志(東大) / 小川 周吾(日立) / 小林 悠記(NEC) / 中原 啓貴(東工大) / 廣瀬 哲也(阪大) / 新居 浩二(フローディア) / 久保木 猛(九大) / 海野 恭平(KDDI総合研究所) / 福嶋 慶繁(名工大) |
| 幹事補佐氏名（英） | Kazuki Ikeda(Hitachi) / / Eiji Arima(Univ. of Tokyo) / Shugo Ogawa(Hitachi) / Yuuki Kobayashi(NEC) / Hiroki Nakahara(Tokyo Inst. of Tech.) / Tetsuya Hirose(Osaka Univ.) / Koji Nii(Floadia) / Takeshi Kuboki(Kyushu Univ.) / Kyohei Unno(KDDI Research) / Norishige Fukushima(Nagoya Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on VLSI Design Technologies / Technical Committee on Dependable Computing / Technical Committee on Computer Systems / Technical Committee on Reconfigurable Systems / Technical Committee on Integrated Circuits and Devices / Technical Committee on Image Engineering / Special Interest Group on System and LSI Design Methodology / Special Interest Group on Embedded Systems / Special Interest Group on System Architecture |
|---|---|
| 本文の言語 | JPN-ONLY |
| タイトル（和） | イジングモデルによる類似誘導部分グラフ同型問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 類似誘導部分グラフ同型問題 |
| キーワード(2)（和/英） | 誘導部分グラフ同型問題 |
| キーワード(3)（和/英） | イジングマシン |
| キーワード(4)（和/英） | イジングモデル |
| キーワード(5)（和/英） | 組合せ最適化問題 |
| 第 1 著者 氏名（和/英） | 吉村 夏一 |
| 第 1 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 2 著者 氏名（和/英） | 多和田 雅師 |
| 第 2 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 3 著者 氏名（和/英） | 田中 宗 |
| 第 3 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 4 著者 氏名（和/英） | 新井 淳也 |
| 第 4 著者 所属（和/英） | NTTソフトウェアイノベーションセンター(略称：NTT) |
| 第 5 著者 氏名（和/英） | 巴 徳瑪 |
| 第 5 著者 所属（和/英） | NTTソフトウェアイノベーションセンター(略称：NTT) |
| 第 6 著者 氏名（和/英） | 八木 哲志 |
| 第 6 著者 所属（和/英） | NTTソフトウェアイノベーションセンター(略称：NTT) |
| 第 7 著者 氏名（和/英） | 内山 寛之 |
| 第 7 著者 所属（和/英） | NTTソフトウェアイノベーションセンター(略称：NTT) |
| 第 8 著者 氏名（和/英） | 戸川 望 |
| 第 8 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 発表年月日 | 2019-11-14 |
| 資料番号 | VLD2019-41,DC2019-65 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | VLD-282,DC-283 |
| ページ範囲 | pp.103-108(VLD), pp.103-108(DC), |
| ページ数 | 6 |
| 発行日 | 2019-11-06 (VLD, DC) |