Exact algorithms for computing the tree edit distance between unordered trees

DOI10.1016/j.tcs.2010.10.002zbMath1206.68224OpenAlexW2064168756MaRDI QIDQ620949

Takeyuki Tamura, Daiji Fukagawa, Atsuhiro Takasu, Tatsuya Akutsu

Publication date: 2 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/149243

zbMATH Keywords

dynamic programmingfixed-parameter algorithmstree edit distanceunordered trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Pattern recognition, speech recognition (68T10)

Related Items

Characterization of random walks on space of unordered trees using efficient metric simulation, Efficient exponential-time algorithms for edit distance between unordered trees, Unnamed Item, New and improved algorithms for unordered tree inclusion, On the complexity of finding a largest common subtree of bounded degree, Covering tree with stars

Cites Work

• Unnamed Item
• Unnamed Item
• On an algorithm of Zemlyachenko for subtree isomorphism
• A survey on tree edit distance and related problems
• On the editing distance between unordered labeled trees
• Some MAX SNP-hard results concerning unordered labeled trees
• A constrained edit distance between unordered labeled trees
• Parametrized complexity theory.
• Fast Algorithms for Finding Nearest Common Ancestors
• The Tree-to-Tree Correction Problem
• Ordered and Unordered Tree Inclusion
• Exact and approximate algorithms for unordered tree matching
• An Optimal Decomposition Algorithm for Tree Edit Distance
• FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES