Fast Algorithms for Computing Tree LCS

DOI10.1007/978-3-540-69068-9_22zbMath1143.68632OpenAlexW1555390699WikidataQ60143034 ScholiaQ60143034MaRDI QIDQ3506956

Michal Ziv-Ukelson, Shay Mozes, Dekel Tsur, Oren Weimann

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69068-9_22

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• New algorithms for the LCS problem
• The longest common subsequence problem revisited
• A faster algorithm computing string edit distances
• Preserving order in a forest in less than logarithmic time and linear space
• Simple and fast linear space computation of longest common subsequences
• Chaining algorithms for multiple genome comparison
• New Algorithm for Ordered Tree-to-Tree Correction Problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Fast Algorithms for Finding Nearest Common Ancestors
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The Tree-to-Tree Correction Problem
• Sparse dynamic programming I
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Local Alignment of RNA Sequences with Arbitrary Scoring Schemes
• An Optimal Decomposition Algorithm for Tree Edit Distance
• Combinatorial Pattern Matching