An Edit Distance between Quotiented Trees

An Edit Distance between Quotiented Trees

0.00 Avg rating0 Votes
Article ID: iaor20118105
Volume: 36
Issue: 1
Start Page Number: 1
End Page Number: 39
Publication Date: May 2003
Journal: Algorithmica
Authors: ,
Keywords: trees
Abstract:

In this paper we propose a dynamic programming algorithm to compare two quotiented trees using a constrained edit distance. A quotiented tree is a tree defined with an additional equivalent relation on vertices and such that the quotient graph is also a tree. The core of the method relies on an adaptation of an algorithm recently proposed by Zhang for comparing unordered rooted trees. This method is currently being used in plant architecture modelling to quantify different types of variability between plants represented by quotiented trees.

Reviews

Required fields are marked *. Your email address will not be published.