二つの木の最大共通部分グラフを求めるアルゴリズム

スポンサーリンク

概要

論文の詳細を見る
最大共通部分グラフ問題は複数のグラフに共通の連結部分グラフのうち,辺の数が最大であるものを求めるというものである.この問題は,化合物の共通部分構造の抽出に応用をもつ重要な問題であるが,一般にはNP-困難である.本論文は,二つの木に対する最大共通部分グラフ問題について考察する.T_a,T_bを任意の二つの木とし,それらの頂点数をそれぞれn_a,n_b(但しn_a≦n_b)とする.本論文では,まずT_a,T_bがともに有向非順序木である場合,ともに無向非順序木である場合のそれぞれについて,最大共通連結部分グラフをO(n_an_b)時間で求めるアルゴリズムを示す.更に,T_a,T_bがともに有向順序木である場合,ともに無向順序木である場合には,それぞれO(n_an_b)時間,O(n_an_blogn_a)時間で最大共通連結部分グラフを求めるアルゴリズムを提案する.
社団法人電子情報通信学会の論文
1994-03-25

著者

関連論文

もっと見る

スポンサーリンク