| 講演名 | 2012/5/7 木に含まれる限定サイズ部分木の列挙 和佐 州洋, 宇野 毅明, 有村 博紀, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年,膨大な量の木やグラフといった半構造データからパターンを発見する要求が高まっている.Ferreiraと,Grossi, Rizzi (ESA'11, 275-286, 2011)は,k-部分木列挙問題を考察し,O(k)ならし時間列挙アルゴリズムを与えた.これは,入力グラフGの中に含まれる非巡回なk頂点の連結部分グラフを重複なくすべて出力する問題である.本稿では,入力を木に限定した場合のk-部分木列挙問題を考察する.主結果として,逆探索法に基づき,この問題に対するk-部分木のならし定数時間列挙アルゴリズムを与える.さらに,木に対するグラフモチーフ問題への応用に問しても議論する. |
| 抄録(英) | By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem, originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011), where an input graph is a tree of n vertices. Based on reverse search technique, we present the first constant amortized time enumeration algorithm that lists all k-subtrees of an input tree in O (1) amortized time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O (k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees. |
| キーワード(和) | 部分木 / 定数時間列挙アルゴリズム / 逆探索法 / グラフモチーフ問題 |
| キーワード(英) | subtree / constant tune enumeration algorithm / reverse search / graph motif problem |
| 資料番号 | Vol.2012-AL-140 No.4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/5/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木に含まれる限定サイズ部分木の列挙 |
| サブタイトル（和） | |
| タイトル（英） | Constant Amortized Time Enumeration of Bounded-Size Subtrees in Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 部分木 / subtree |
| キーワード(2)（和/英） | 定数時間列挙アルゴリズム / constant tune enumeration algorithm |
| キーワード(3)（和/英） | 逆探索法 / reverse search |
| キーワード(4)（和/英） | グラフモチーフ問題 / graph motif problem |
| 第 1 著者 氏名（和/英） | 和佐 州洋 / KUNIHIRO WASA |
| 第 1 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology |
| 第 2 著者 氏名（和/英） | 宇野 毅明 / TAKEAKI UNO |
| 第 2 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 第 3 著者 氏名（和/英） | 有村 博紀 / HIROKI ARIMURA |
| 第 3 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Hokkaido University, Graduate School of Information Science and Technology |
| 発表年月日 | 2012/5/7 |
| 資料番号 | Vol.2012-AL-140 No.4 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 24 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |