An Optimal Decomposition Algorithm for Tree Edit Distance

DOI10.1007/978-3-540-73420-8_15MaRDI QIDQ5428805zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_15

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• An optimal decomposition algorithm for tree edit distance
• Efficient computation of the tree edit distance
• Decomposition algorithms for the tree edit distance problem
• Edit distance between unrooted trees in cubic time
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(34)

• An edit distance between quotiented trees
• Resequencing a set of strings based on a target string
• Covering tree with stars
• Approximating tree edit distance through string edit distance
• Algorithms for local similarity between forests
• Efficient exponential-time algorithms for edit distance between unordered trees
• Decomposition algorithms for the tree edit distance problem
• An optimal decomposition algorithm for tree edit distance
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Fast Algorithms for Computing Tree LCS
• Analysis of tree edit distance algorithms
• An Improved Algorithm for Tree Edit Distance Incorporating Structural Linearity
• Fast RNA Structure Alignment for Crossing Input Structures
• A survey on tree matching and XML retrieval
• Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
• Edit distance between unrooted trees in cubic time
• Efficient computation of the tree edit distance
• Approximate joins for XML at label level
• \(1+\varepsilon\) approximation of tree edit distance in quadratic time
• Fast RNA structure alignment for crossing input structures
• Combinatorial Pattern Matching
• Fast algorithms for the unit cost editing distance between trees
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
• Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
• On the hardness of computing the edit distance of shallow trees
• Exact algorithms for computing the tree edit distance between unordered trees
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• Approximation and special cases of common subtrees and editing distance
• Finding common RNA pseudoknot structures in polynomial time
• Fast algorithms for computing tree LCS
• A theory of subtree matching and tree kernels based on the edit distance concept
• Finding common structured patterns in linear graphs
• Faster algorithms for guided tree edit distance
• Improved approximation of the largest common subtree of two unordered trees of bounded height

This page was built for publication: An Optimal Decomposition Algorithm for Tree Edit Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428805)