| 講演名 | 2005-04-18 パス頻度ベクトルからのグラフ推定問題の困難性について 阿久津 達也, 深川 大路, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ラベル付き頂点から成るパスの出現頻度から元のグラフを推定する問題は, 機械学習の分野においてpre-image問題として知られる, 特徴ベクトルから元のデータを再構成する問題と深く関係している. グラフが次数が限定された木で与えられるパスの長さが定数で抑えられる場合, このグラフ推定問題がグラフのサイズについて多項式時間で解けることを示す. その一方で, 次数が限定された平面グラフについてこの問題が強NP完全であることを示す. |
| 抄録(英) | We consider the problem of inferring a graph (and a sequence) from the numbers of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs in machine learning : to reconstruct a graph from its feature space representation. We show that this problem can be solved in polynomial time of the size of an output graph if graphs are trees of bounded degree and the lengths of given paths are bounded by a constant. On the other hand, we show that this problem is strongly NP-complete even for planer graphs of bounded degree. |
| キーワード(和) | グラフ推定問題 / パス頻度ベクトル / 強NP完全 |
| キーワード(英) | graph inference / path frequency / pre-image / strongly NP-complete |
| 資料番号 | COMP2005-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | パス頻度ベクトルからのグラフ推定問題の困難性について |
| サブタイトル（和） | |
| タイトル（英） | On the Complexity of Inferring a Graph from Path Frequency |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ推定問題 / graph inference |
| キーワード(2)（和/英） | パス頻度ベクトル / path frequency |
| キーワード(3)（和/英） | 強NP完全 / pre-image |
| 第 1 著者 氏名（和/英） | 阿久津 達也 / Tatsuya AKUTSU |
| 第 1 著者 所属（和/英） | 京都大学化学研究所バイオインフォマティクスセンター Bioinformatics Center, Institute for Chemical Research, Kyoto University |
| 第 2 著者 氏名（和/英） | 深川 大路 / Daiji FUKAGAWA |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-7 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |