Title :
A Dynamic Programming A* Algorithm for Computing Unordered Tree Edit Distance
Author :
Yoshino, Tomonobu ; Higuchi, Suemi ; Hirata, Kazufumi
Author_Institution :
Grad. Sch. of Comput. Sci. & Syst. Eng., Kyushu Inst. of Technol., Iizuka, Japan
fDate :
Aug. 31 2013-Sept. 4 2013
Abstract :
In this paper, we improve the A* algorithm for computing the edit distance between rooted labeled unordered trees designed by Higuchi et al. (2012) by using the dynamic programming technique, which we call the dynamic programming A* algorithm. Then, we give experimental results for glycan data by comparing the dynamic programming A* algorithm with the original A* algorithm, the exhaustive search algorithm and the clique-based algorithm.
Keywords :
dynamic programming; trees (mathematics); clique-based algorithm; dynamic programming A* algorithm; exhaustive search algorithm; rooted labeled unordered trees; unordered tree edit distance computing; Informatics; A* algorithm; Tai mapping; dynamic programming A* algorithm; unordered tree edit distance;
Conference_Titel :
Advanced Applied Informatics (IIAIAAI), 2013 IIAI International Conference on
Conference_Location :
Los Alamitos, CA
Print_ISBN :
978-1-4799-2134-8
DOI :
10.1109/IIAI-AAI.2013.71
