Fast algorithms for computing tree LCS

DOI10.1016/j.tcs.2009.07.011zbMath1187.68684OpenAlexW2069957592WikidataQ60143026 ScholiaQ60143026MaRDI QIDQ732018

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

Publication date: 9 October 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.011

zbMATH Keywords

ordered treessparse dynamic programmingtree edit distancelargest common subforesttree LCS

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items

On almost Monge all scores matrices ⋮ Unnamed Item

Cites Work

• 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
• Generalized LCS
• 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
• An Optimal Decomposition Algorithm for Tree Edit Distance
• Combinatorial Pattern Matching
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item