電子情報通信学会総合大会講演要旨
D-8-12
グラフ集合に対する部分グラフ同型判定処理のための提案
◎神谷洋平・世木博久(名工大)
二つのグラフが与えられた時, 一方のグラフがもう一方のグラフに含まれるかを判定する問題を部分グラフ同型判定問題といい, 科学, 工学分野において広く応用さ
れている. Messmerらは, あるグラフのグラフ集合に対する部分グラフ同型判定問題を, 分解データと呼ばれる特殊なデータ構造を利用して効率的に解くアルゴリズムを提案している. また, 分解データへの変換方法の工夫によるMessmerらの手法の改良が西村らによって提案されている.
本稿では, Messmer らの手法で最も時間のかかっている結合処理と呼ばれる部分を改良する手法を提案する.