文献

J-GLOBAL ID：201502286392223363   整理番号：15A0725873

頂点誘導部分グラフを列挙索引化するフロンティア法

Frontier Method for Enumerating and Indexing the Vertex Induced Subgraphs

著者 (2件)： 鈴木浩史 (北大 大学院情報科学研究科) ,  湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 15(COMP2015 1-5)  ページ： 15-20  発行年： 2015年04月16日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 頂点誘導部分グラフとは,グラフG=(V,E)の頂点部分集合U⊆Vを与えたとき,両端点がUに含まれる頂点であるEの辺を辺集合とする部分グラフである。本稿では,与えられたグラフ中で頂点誘導部分グラフとなりうる辺の組合せを列挙し,Zero-suppressed Binary Decision Diagram(ZDD)というデータ構造により索引化することを試みる。ZDDの構築には,ありうる辺の組合せを全て索引化したZDDを,一括してトップダウンに構築するフロンティア法と呼ばれる技法を用いる。我々は,与えられたグラフの任意の辺集合が頂点誘導部分グラフとなるための条件を明らかにし,それによりフロンティア法に基づく列挙索引化手法を実現した。計算実験の結果,本手法は日本の都道府県隣接関係を基にしたグラフ上で,22,744,781,201,224個もの頂点誘導部分グラフを,わずか0.01秒で列挙しZDDにより索引化した。(著者抄録)

シソーラス用語： *頂点 ,  *誘導 ,  *部分グラフ ,  *能力 ,  *索引 ,  グラフ ,  部分集合 ,  図表 ,  データ構造
準シソーラス用語： 決定ダイアグラム ,  *語列挙

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (6件)：

• S. Minato: ”Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems”, In Proc. of 30th ACM/IEEE Design Automation Conference (DAC'93), pp. 272-277, Jun. 1993.
• Norihito Yasuda, Masaaki Nishino, and Shin-ichi Minato On the Size of the Zero-Suppressed Binary Decision Diagram that Represents All the Subtrees in a Tree, In workshop note of the fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2014), pp. 3-9., 2014年05月
• 川原 純,湊 真一. 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化. 信学技報, vol.112, no.93, COMP2012-12, pp.1-7, 2012.
• 川原 純,湊 真一 グラフ列挙索引化技法の種々の問題への適用, オペレーションズ・リサーチ(2012年11月号), Vol.57 No.11, 2012年11月
• D.E.Knuth. The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Vol. 4, fascicle 1. Addison-Wesley, 2009.

タイトルに関連する用語 (4件)： 頂点 ,  誘導 ,  部分グラフ ,  索引