講演抄録/キーワード |
講演名 |
2015-04-23 14:10
頂点誘導部分グラフを列挙索引化するフロンティア法 ○鈴木浩史・湊 真一(北大) COMP2015-3 |
抄録 |
(和) |
頂点誘導部分グラフとは,グラフ$G=(V,E)$の頂点部分集合$U subseteq V$を与えたとき,両端点が$U$に含まれる頂点である$E$の辺を辺集合とする部分グラフである.
本稿では,与えられたグラフ中で頂点誘導部分グラフとなりうる辺の組合せを列挙し,Zero-suppressed Binary Decision Diagram(ZDD)というデータ構造により索引化することを試みる.ZDDの構築には,ありうる辺の組合せを全て索引化したZDDを,一括してトップダウンに構築するフロンティア法と呼ばれる技法を用いる.我々は,与えられたグラフの任意の辺集合が頂点誘導部分グラフとなるための条件を明らかにし,それによりフロンティア法に基づく列挙索引化手法を実現した.計算実験の結果,本手法は日本の都道府県隣接関係を基にしたグラフ上で,22744781201224個もの頂点誘導部分グラフを,わずか0.01秒で列挙しZDDにより索引化した. |
(英) |
(Not available yet) |
キーワード |
(和) |
ZDD / フロンティア法 / 頂点誘導部分グラフ / 列挙問題 / / / / |
(英) |
ZDD / Frontier Method / Vertex Induced Subgraph / Enumeration Problem / / / / |
文献情報 |
信学技報, vol. 115, no. 15, COMP2015-3, pp. 15-20, 2015年4月. |
資料番号 |
COMP2015-3 |
発行日 |
2015-04-16 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2015-3 |