This paper proposes algorithms for computing three kinds of distances between two rooted and unordered trees (R-trees) and that between two unrooted and unordered trees (trees). Those distances are that based on strongly structure preserving mapping (SSPD), that based on closest common ancestor mapping (CD), and that based on maximal closest common ancestor mapping (MCD), respectively. The time and space complexities to compute the distances between two R-trees Ta and Tb are OT(maNaNb) and OS(NaNb), respectively, and those to compute the distances between two trees Ta and Tb are OT(max(ma,mb)2NaNb) and OS(NaNb), respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. The proposed algorithms for SSPD and CD are more efficient than the algorithms proposed before. MCD is newly proposed in this paper. Those distances can be applied to structure-activity studies and various structure comparison problems. [In Japanese.]
