• DocumentCode
    3509724
  • 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
  • fYear
    2013
  • fDate
    Aug. 31 2013-Sept. 4 2013
  • Firstpage
    135
  • Lastpage
    140
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Advanced Applied Informatics (IIAIAAI), 2013 IIAI International Conference on
  • Conference_Location
    Los Alamitos, CA
  • Print_ISBN
    978-1-4799-2134-8
  • Type

    conf

  • DOI
    10.1109/IIAI-AAI.2013.71
  • Filename
    6630333
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3509724