順序がない木の距離を求めるアルゴリズム

劉 紹明  田中 栄一  

誌名
電子情報通信学会論文誌 A   Vol.J78-A    No.10    pp.1358-1371
発行日: 1995/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: グラフとネットワーク
キーワード: 
,  距離,  アルゴリズム,  計算量,  構造,  構造活性相関,  

本文: PDF(836.6KB)>>
論文を購入



あらまし: 
本論文は根があり順序がない木(R木と言う)および根がなく順序がない木(単に木と言う)について,それぞれ,強構造保存写像に基づく距離(SSPD),C写像に基づく距離(CD)および極大C写像に基づく距離(MCD),の3種類の距離の計算法を提案している.R木の場合,いずれも,時間計算量はOTmaNaNb),空間計算量はOSNaNb)である.木の場合,3種類の距離の計算法の時間計算量はOT(max(mamb2NaNb),空間計算量はOSNaNb)である.ここで,二つのR木,あるいは二つの木をTaTbとするとき,mamb),NaNb)はそれぞれTaTb)の頂点の最大次数,TaTb)の頂点数である.SSPD,CDの計算法は,R木および木の場合とも,従来の計算法より効率が良く,MCDは本論文で提案した距離である.R木および木の距離は,化学で研究されている構造・活性問題をはじめとして,多くの構造比較問題に応用できる.