平面に埋め込まれた木の間の距離およびその計算法

• 田中 栄一

  神戸大学 工学部

書誌事項

タイトル別名

• Metrics between Trees Embedded in a Plane and Their Computing Methods

抄録

平面に埋め込まれた木は根がなく巡回的順序がある木(CO-木)と定義できる.本論文はCO-木間の三種類の距離を定義し,それぞれの計算法を提案する.三種類の距離はそれぞれTai写像に基づく距離,構造保存写像に基づく距離と強構造保存写像に基づく距離である.簡単のため,三種類の距離をそれぞれTai距離(TD),構造保存距離(SPD)と強構造保存距離(SSPD)と呼ぶ.それらの距離の定義およびそれぞれの計算法は従来の定義および計算法より簡単である.本論文で定義したTDおよびSPDは従来の定義より大きい値を取ることがあり,換言すれば,構造の相違に対して敏感である.二つのSSPDの定義は等価である.CO-木T_aとT_bの間のTD,SPDおよびSSPDの計算に要する時間計算量はそれぞれO_T(N^2_aN^2_b),O_T(m_aN_aN^2_b)およびO_T(m_am_bN_aN_b)である.ここで,N_a(N_b)とm_a(m_b)はそれぞれT_a(T_b)の頂点数とT_a(T_b)の頂点の最大次数を表す.三つの計算法の空間計算量は共にO_S(N_aN_b)である.
A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree (C0-tree). This paper describes new definitions of three distances between CO-trees and their computing methods. The proposed distances are based on the Tai mapping, the structure preserving mapping and the strongly structure preserving mapping, respectively, and are called the Tai distance (TD), the structure preserving distance (SPD) and the strongly structure preserving distance (SSPD), respectively. The definitions of distances and their computing methods are simpler than those of the old definitions and computing methods, respectively. TD and SPD by the new definitions are more sensitive than those by the old ones, and SSPDs by both definitions are equivalent. The time complexities of computing TD, SPD and SSPD between CO-trees T_a and T_b are O_T(N^2_aN^2_b), O_T(m_aN_aN_^2_b) and O_T(m_am_bN_aN_b), respectively, where N_a(N_b) and m_a(m_b) are the number of vertices in tree T_a(T_b) and the maximum degree of a vertex in T_a(T_b), respectively. The space complexities of these methods are O_S(N_aN_b).

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 48 31-38, 1995-11-17

  一般社団法人情報処理学会

詳細情報

• CRID: 1570854177186457600
• NII論文ID: 110002812323
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles