The Distances between Unrooted and Cyclically Ordered Trees and Their Computing Methods

概要

論文の詳細を見る
Several distances between trees have been proposed. However, most of the reports on distances have dealt with rooted and ordered trees. This paper proposes two distances between unrooted and cyclically ordered trees (CO-trees) and their computing methods. A CO-tree is a tree embedded in a plane. These distances are defined based on Tai's mapping (TM) and a strongly structure preserving mapping (SSPM) between CO-trees. The time complexities to compute the distances between two CO-trees T_a and T_b are O_T(N^aN^b) for the distance based on a TM and O_T(m_am_bN_aN_b) for that on an SSPM, respectively, where m_a(m_b) and N_a(N_b) are the largest degree of a vertex and the number of vertices of T_a(T_b), respectively. The space complexities of both methods are O_S(N_aN_b). Those distances can be applied to the clustering of CO-trees.
社団法人電子情報通信学会の論文
1994-10-25