Exact algorithms for computing tree edit distance between unordered trees

• 阿久津, 達也

• Fukagawa, Daiji

• Takasu, Atsuhiro

• Tamura, Takeyuki

書誌事項

タイトル別名

• Exact algorithms for computing the tree edit distance between unordered trees

抄録

This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in O(2.62^k⋅poly(n)) time and O(n^2) space, where the parameter k is the maximum bound of the edit distance and n is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant

収録刊行物

• Theoretical Computer Science

  Theoretical Computer Science 412 (4-5), 352-364, 2011-02-04

  Elsevier B.V.

キーワード

• Tree edit distance
• Fixed-parameter algorithms
• Dynamic programming
• Unordered trees

詳細情報

• CRID: 1050564285677005696
• NII論文ID: 120003517914
• NII書誌ID: AA00862688
• ISSN: 03043975
• DOI: 10.1016/j.tcs.2010.10.002
• HANDLE: 2433/149243
• Web Site: https://api.elsevier.com/content/article/PII:S0304397510005463?httpAccept=text/xml
• Web Site: https://api.elsevier.com/content/article/PII:S0304397510005463?httpAccept=text/plain
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN