- 著者
-
劉 紹明
田中 栄一
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. A, 基礎・境界 (ISSN:09135707)
- 巻号頁・発行日
- vol.78, no.10, pp.1358-1371, 1995-10-25
- 被引用文献数
-
4
本論文は根があり順序がない木(R木と言う)および根がなく順序がない木(単に木と言う)について,それぞれ,強構造保存写像に基づく距離(SSPD),C写像に基づく距離(CD)および極大C写像に基づく距離(MCD),の3種類の距離の計算法を提案している.R木の場合,いずれも,時間計算量はO_T(m_aN_aN_b),空間計算量はO_s(N_aN_b)である.木の場合,3種類の距離の計算法の時間計算量はO_T(max(m_a,m_b)^2N_aN_b),空間計算量はO_s(N_aN_b)である.ここで,二つのR木,あるいは二つの木をT_a,T_bとするとき,m_a(m_b),N_a(N_b)よそれぞれT_a(T_b)の頂点の最大次数,T_a(T_b)の頂点数である.SSPD,CDの計算法は,R木および木の場合とも,従来の計算法より効率が良く,MCDは本論文で提案した距離である.R木および木の距離は,化学で研究されている構造・活性問題をはじめとして,多くの構造比較問題に応用できる.