- 著者
-
Liu Shaoming
Tanaka Eiichi
Masuda Sumio
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- IEICE transactions on information and systems (ISSN:09168532)
- 巻号頁・発行日
- vol.77, no.10, pp.1094-1105, 1994-10-25
- 被引用文献数
-
5
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.