文献

J-GLOBAL ID：201702230899110710   整理番号：17A1619307

圧縮された表現を含むすべての制約付き部分グラフを列挙する為のフロンティアベース検索

Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation

著者 (4件)： KAWAHARA Jun (Graduate School of Information Science, Nara Institute of Science and Technology) ,  INOUE Takeru (NTT Network Innovation Laboratories, NTT Corporation) ,  IWASHITA Hiroaki (Fujitsu Laboratories Limited) ,  MINATO Shin-ichi (Graduate School of Information Science and Technology, Hokkaido University)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E100.A  号： 9  ページ： 1773-1784(J-STAGE)  発行年： 2017年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 部分グラフ列挙問題では,時間複雑度が部分グラフの数よりはるかに少ない非常に効率的なアルゴリズムが提案されている。部分グラフの数は,入力グラフのサイズに伴って指数関数的に増加することが出来るが,これ等のアルゴリズムは,圧縮された表現を利用して列挙された部分グラフをコンパクトに出力,維持し,時間及び空間の複雑さを低減する。しかし,それ等は,幾つかの特定のタイプの部分グラフ,例えばパス,又はツリーのみを列挙する様に設計されている。本論文は,フロンティアベースの検索と呼ばれるアルゴリズムフレームワークを提案し,効率を失うことなくこれ等のアルゴリズムを一般化した。本フロンティアベースの検索は,制約付きサブグラフ列挙を含む様々な実際の問題を解決する為に使用出来る。(翻訳著者抄録)

シソーラス用語： *部分グラフ ,  *検索 ,  *データ圧縮 ,  アルゴリズム ,  構成
準シソーラス用語： グラフアルゴリズム ,  *グラフ検索 ,  サブグラフ ,  フレームワーク ,  *情報圧縮

著者キーワード (4件)： zero-suppressed binary decision diagram ,  froniter-based search ,  enumeration algorithm ,  subgraph

分類 (2件)： 計算理論  (JB02000A) ,  検索システム  (AC06030D)

引用文献 (21件)：

• [1] R.C. Read and R.E. Tarjan, “Bounds on backtrack algorithms for listing cycles, paths, and spanning trees,” Networks, vol.5, pp.237-252, 1975.
• [2] S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol.27, no.4, pp.619-632, Oct. 1980. 10.1145/322217.322220
• [3] D. Avis and K. Fukuda, “Reverse search for enumeration,” Discrete Appl. Math., vol.65, no.1-3, pp.21-46, 1993. 10.1016/0166-218x(95)00026-n
• [4] K. Sekine, H. Imai, and S. Tani, “Computing the Tutte polynomial of a graph of moderate size,” Proc. 6th International Symposium on Algorithms and Computation (ISAAC), pp.224-233, 1995. 10.1007/bfb0015427
• [5] S. Minato, T. Uno, and H. Arimura, “LCM over ZBDDs: Fast generation of very large-scale frequent itemsets using a compact graph-based representation,” in Advances in Knowledge Discovery and Data Mining, ed. T. Washio, E. Suzuki, K.M. Ting, and A. Inokuchi, Lecture Notes in Computer Science, vol.5012, pp.234-246, Springer Berlin Heidelberg, 2008. 10.1007/978-3-540-68125-0_22

タイトルに関連する用語 (4件)： 表現 ,  制約 ,  部分グラフ ,  検索