| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-05-11 10:40 ZDDを用いたグラフ細分構造の列挙索引化 ○中畑 裕・川原 純（京大）・堀山貴史（埼玉大）・湊 真一（京大）  COMP2019-3 |
|
| 抄録 | （和） | グラフ $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 / / | |
| 文献情報 | 信学技報, vol. 119, no. 21, COMP2019-3, pp. 51-58, 2019年5月. | |
| 資料番号 | COMP2019-3 | |
| 発行日 | 2019-05-03 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-3 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2019-05-10 - 2019-05-11 |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2019-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 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 |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-05-11 10:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-3 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.21 |
| ページ範囲 | pp.51-58 |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |
[研究会発表申込システムのトップページに戻る]