文献

J-GLOBAL ID：201202233846411480   整理番号：12A0924171

木に含まれる限定サイズ部分木の列挙

Constant Amortized Time Enumeration of Bounded-Size Subtrees in Trees

著者 (3件)： 和佐州洋 (北大 大学院情報科学研究科) ,  宇野毅明 (国立情報学研) ,  有村博紀 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 24(COMP2012 8-11)  ページ： 25-32  発行年： 2012年05月07日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,膨大な量の木やグラフといった半構造データからパターンを発見する要求が高まっている。Ferreiraと,Grossi,Rizzi(ESA’11,275-286,2011)は,k-部分木列挙問題を考察し,O(k)ならし時間列挙アルゴリズムを与えた。これは,入力グラフGの中に含まれる非巡回なk頂点の連結部分グラフを重複なくすべて出力する問題である。本稿では,入力を木に限定した場合のk-部分木列挙問題を考察する。主結果として,逆探索法に基づき,この問題に対するk-部分木のならし定数時間列挙アルゴリズムを与える。さらに,木に対するグラフモチーフ問題への応用に関しても議論する。(著者抄録)

シソーラス用語： *木【グラフ】 ,  発見 ,  データ ,  頂点 ,  主題 ,  *抽出
準シソーラス用語： *パターンマイニング ,  パターン発見 ,  モチーフ ,  半構造データ ,  *部分木

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (15件)：

• ABITEBOUL, S. Data on the Web : From Relations to Semistructured Data and XML. 1999
• ARIMURA, H. Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems. Proc. SDM'09. 2009, 1087-1098
• ASAI, T. Efficient substructure discovery from large semi-structured data. SDM, 2002. 2002
• AVIS, D. Reverse search for enumeration. Discrete Applied Mathematics. 1993, 65, 21-46
• CORMEN, T. H. Introduction to Algorithms. 2001

タイトルに関連する用語 (3件)： 木 ,  サイズ ,  部分木