WEKO3
アイテム
属性付きグラフマッチングアルゴリズムの効率的な実装
https://ipsj.ixsq.nii.ac.jp/records/31753
https://ipsj.ixsq.nii.ac.jp/records/3175328e589d7-1519-4402-8378-dcee8ca5945d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL06105008.pdf (363.4 kB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-03-17 | |||||||
| タイトル | ||||||||
| タイトル | 属性付きグラフマッチングアルゴリズムの効率的な実装 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Efficient Implementation of Attribute-Graph Matching Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Electro-Communications | ||||||||
| 著者名 |
森田, 昭広
× 森田, 昭広
|
|||||||
| 著者名(英) |
Akihiro, MORITA
× Akihiro, MORITA
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | グラフのマッチング問題は一般に計算量が膨大であるが，問題固有の属性情報などを用いて効率的な探索を実現できる可能性がある．本研究では，グラフマッチング問題が入力2グラフから生成される積グラフの最大クリークを抽出する問題へ還元できることに着目し，その効率化のために2つの属性情報利用アルゴリズムを考案した．1つ目はクリーク抽出の探索過程で属性情報を用いて探索領域を削減する方法，2つ目は積グラフの生成時に属性情報を用いて積グラフの規模自体を抑制する方法である．これらを計算機実験によって比較検証した結果，双方共に有効であるが，特に後者の有効性が顕著であることを確認した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2006, 号 30(2006-AL-105), p. 49-54, 発行日 2006-03-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
