2026-05-21T17:44:26Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00018825 2025-01-22T22:34:18Z 1164:1165:1170:1171

ラベル付きグラフのフィルタリングのための行列サイズ縮小手法 Reduction of Matrix Order for Filtering Labeled Graphs 長屋, 未来 片山, 薫 Hideki, NAGAYA Kaoru, KATAYAMA 画像における特徴量抽出、化学式における類似構造の検出などに部分グラフ同型判定は応用できる。しかし部分グラフ同型判定問題は NP 完全であり、大規模なグラフを扱う場合、実用時間内に解くことが困難である。我々は部分グラフ同型判定の前処理として、対称行列の固有値に関する事実(Cauchy の interlace 定理)を利用することを提案し、その有効性を確認した。固有値計算に必要な行列サイズを縮小する事で interlace 定理を利用するためのコストを減らし、interlace 定理の判定精度を改善する事は有効であると考えられる。本稿では、ラベルを利用してグラフをフィルタリングすると共に、グラフを表現する行列のサイズを縮小する手法を提案する。 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. 情報処理学会 2007-07-04 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/18825 AN10112482 情報処理学会研究報告データベースシステム（DBS） 2007 65(2007-DBS-143) 467 472 https://ipsj.ixsq.nii.ac.jp/record/18825/files/IPSJ-DBS07143079.pdf application/pdf 839.3 kB 2009-07-04