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

劉　紹明  田中　栄一  

誌名
電子情報通信学会論文誌 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木の場合，いずれも，時間計算量はOT（maNaNb），空間計算量はOS（NaNb）である．木の場合，3種類の距離の計算法の時間計算量はOT（max（ma，mb）2NaNb），空間計算量はOS（NaNb）である．ここで，二つのR木，あるいは二つの木をTa，Tbとするとき，ma（mb），Na（Nb）はそれぞれTa（Tb）の頂点の最大次数，Ta（Tb）の頂点数である．SSPD，CDの計算法は，R木および木の場合とも，従来の計算法より効率が良く，MCDは本論文で提案した距離である．R木および木の距離は，化学で研究されている構造・活性問題をはじめとして，多くの構造比較問題に応用できる．