Metrics between Trees Embedded in a Plane and Their Computing Methods (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
A tree embedded in a plane can be characterized as an unrooted and cyclically ordered tree ( CO-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 comp1exities 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).
1996-04-25