ラベル付きグラフのフィルタリングのための行列サイズ縮小手法

• Item type: SIG Technical Reports(1)
• 公開日: 2007-07-04
• タイトル: ラベル付きグラフのフィルタリングのための行列サイズ縮小手法
• タイトル / 言語: en
• タイトル: Reduction of Matrix Order for Filtering Labeled Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 首都大学東京システムデザイン研究科
• 著者所属: 首都大学東京システムデザイン研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of System Design, Tokyo Metropolitan University
• 著者所属(英): en
• 著者所属(英): Graduate School of System Design, Tokyo Metropolitan University
• 著者名: 長屋, 未来; 片山, 薫
• 著者名(英): Hideki, NAGAYA; Kaoru, KATAYAMA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 画像における特徴量抽出、化学式における類似構造の検出などに部分グラフ同型判定は応用できる。しかし部分グラフ同型判定問題は NP 完全であり、大規模なグラフを扱う場合、実用時間内に解くことが困難である。我々は部分グラフ同型判定の前処理として、対称行列の固有値に関する事実(Cauchy の interlace 定理)を利用することを提案し、その有効性を確認した。固有値計算に必要な行列サイズを縮小する事で interlace 定理を利用するためのコストを減らし、interlace 定理の判定精度を改善する事は有効であると考えられる。本稿では、ラベルを利用してグラフをフィルタリングすると共に、グラフを表現する行列のサイズを縮小する手法を提案する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: It is often used to solve the subgraph isomorphism problem in various application such as retrieval for a chemical formula, feature extraction from pictures. This problem is NP-complete and require large computation cost to solve it. We suggested to use the fact concerning the symmetric eigenvalue (Cauchy's interlace theorem) as a preprocessing of the subgraph isomorphism. It is effective to reduce order of the matrix for decreasing the cost to calculate eigenvalue. In this paper, we suggest a method reducing order of the matrix while filtering labeled graphs by using label of graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2007, 号 65(2007-DBS-143), p. 467-472, 発行日 2007-07-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会