| 講演名 | 2019-05-11 ZDDを用いたグラフ細分構造の列挙索引化 中畑 裕(京大), 川原 純(京大), 堀山 貴史(埼玉大), 湊 真一(京大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフ $H$ の細分とは，$H$ の各辺にいくつかの頂点を挿入して得られるグラフである．本研究では，グラフ $G$, $H$ が与えられたとき，$G$ の部分グラフであって $H$ の細分と同型であるものを効率よく列挙する方法を提案する．提案手法はデータ構造ZDDを用いて膨大な解の集合を圧縮保持する．さらに，本手法の応用として，細分を用いて特徴づけられる部分グラフ（平面的グラフや外平面的グラフなど）を列挙するための一般的なアルゴリズムを提案する．計算機実験により，提案手法が，バックトラック法に基づくアルゴリズムよりも高速に動作することを示す． |
| 抄録(英) | A subdivision of a graph $H$ is a graph obtained by inserting some vertices into each edge of $H$. In this paper, when we are given graphs $G$ and $H$, we propose an algorithm to enumerate subgraphs of $G$ each of which is isomorphic to a subdivision of $H$. We use a data structure, a zero-suppressed binary decision diagram, to deal with a large set of solutions in a compressed way. In addition, we propose a general algorithm to enumerate subgraphs characterized by subdivisions (e.g., planar and outerplanar graphs). Computational experiments show that our algorithm runs faster than a backtracking algorithm. |
| キーワード(和) | グラフアルゴリズム / 列挙 / 細分 / 決定グラフ / ZDD / フロンティア法 |
| キーワード(英) | Graph algorithm / Enumeration / Subdivision / Decision diagram / ZDD / Frontier-based search |
| 資料番号 | COMP2019-3 |
| 発行日 | 2019-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) / 瀧本 英二(九州大学) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ZDDを用いたグラフ細分構造の列挙索引化 |
| サブタイトル（和） | |
| タイトル（英） | Enumerating and Indexing Graph Subdivisions using Zero-suppressed Binary Decision Diagrams |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフアルゴリズム / Graph algorithm |
| キーワード(2)（和/英） | 列挙 / Enumeration |
| キーワード(3)（和/英） | 細分 / Subdivision |
| キーワード(4)（和/英） | 決定グラフ / Decision diagram |
| キーワード(5)（和/英） | ZDD / ZDD |
| キーワード(6)（和/英） | フロンティア法 / Frontier-based search |
| 第 1 著者 氏名（和/英） | 中畑 裕 / Yu Nakahata |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 2 著者 氏名（和/英） | 川原 純 / Jun Kawahara |
| 第 2 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 3 著者 氏名（和/英） | 堀山 貴史 / Takashi Horiyama |
| 第 3 著者 所属（和/英） | 埼玉大学(略称：埼玉大) Saitama University(略称：Saitama Univ.) |
| 第 4 著者 氏名（和/英） | 湊 真一 / Shin-ichi Minato |
| 第 4 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 発表年月日 | 2019-05-11 |
| 資料番号 | COMP2019-3 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-21 |
| ページ範囲 | pp.51-58(COMP), |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |