An optimal decomposition algorithm for tree edit distance

DOI10.1145/1644015.1644017zbMath1300.68057arXivcs/0604037WikidataQ60143028 ScholiaQ60143028MaRDI QIDQ2930275

Erik D. Demaine, Oren Weimann, Benjamin Rossman, Shay Mozes

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0604037

zbMATH Keywords

dynamic programming; ordered trees; edit distance; tree edit distance; decomposition strategy

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68P05: Data structures

Related Items

Alignment distance of regular tree languages, Alignment distance of regular tree languages, Efficient chaining of seeds in ordered trees, Algorithms for finding a most similar subforest, Mining approximate patterns with frequent locally optimal occurrences, Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems, An improved algorithm for tree edit distance with applications for RNA secondary structure comparison, On the complexity of finding a largest common subtree of bounded degree, Tai mapping hierarchy for rooted labeled trees through common subforest, Efficient exponential-time algorithms for edit distance between unordered trees, Efficient Chaining of Seeds in Ordered Trees, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees