Paper Info
Title
A constrained edit distance algorithm between semi-ordered trees
Abstract
In this paper, we propose a formal definition of a new class oftrees called semi-ordered trees and a polynomial dynamicprogramming algorithm to compute a constrained edit distancebetween such trees. The core of the method relies on a similarapproach to compare unordered [Kaizhong Zhang, A constrained editdistance between unordered labeled trees, Algorithmica 15 (1996)205-222] and ordered trees [Kaizhong Zhang, Algorithms for theconstrained editing distance between ordered labeled trees andrelated problems, Pattern Recognition 28 (3) (1995) 463-474]. Themethod is currently applied to evaluate the similarity betweenarchitectures of apple trees [Vincent Segura, Aida Ouangraoua,Pascal Ferraro, Evelyne Costes, Comparison of tree architectureusing tree edit distances: Application to two-year-old apple tree,Euphytica 161 (2007) 155-164].
Year
DOI
Venue
2009
10.1016/j.tcs.2008.11.022
Theor. Comput. Sci.
Keywords
DocType
Volume
Semi-ordered trees,Vincent Segura,Theory of computation,distance algorithm,trees andrelated problem,Pattern Recognition,Kaizhong Zhang,Dynamic programming,two-year-old apple tree,Tree editing,apple tree,Evelyne Costes,semi-ordered tree,Aida Ouangraoua,Pascal Ferraro
Journal
410
Issue
ISSN
Citations 
8-10
Theoretical Computer Science
2
PageRank 
References 
Authors
0.38
6
2
Name
Order
Citations
PageRank
Aïda Ouangraoua19415.93
Pascal Ferraro27711.54