著者

森田 昭広 古賀 久志 渡辺 俊典 横山 貴紀

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.30, pp.49-54, 2006-03-17

---

グラフのマッチング問題は一般に計算量が膨大であるが,問題固有の属性情報などを用いて効率的な探索を実現できる可能性がある.本研究では,グラフマッチング問題が入力2グラフから生成される積グラフの最大クリークを抽出する問題へ還元できることに着目し,その効率化のために2つの属性情報利用アルゴリズムを考案した.1つ目はクリーク抽出の探索過程で属性情報を用いて探索領域を削減する方法,2つ目は積グラフの生成時に属性情報を用いて積グラフの規模自体を抑制する方法である.これらを計算機実験によって比較検証した結果,双方共に有効であるが,特に後者の有効性が顕著であることを確認した.Graph matching problem has a very high computational complexity. But we can reduce it by exploiting domain-specific information such as object's attributes. In this research, where we solve the graph matching problem by reducing it into a maximum clique problem in a product graph generated from the two input graphs, we propose two algorithms, both exploiting attribute information. One is the method of decreasing the search space by using attribute information in the process of maximum clique search. The other is the method of decreasing the size of the product graph by using attribute information during the product graph generation. Through experiments we showed that, although both are effective, the latter dominates the former.