Fast algorithms for computing tree LCS

DOI10.1016/J.TCS.2009.07.011MaRDI QIDQ732018zbMATH OpenOpenAlexWikidataFDO

Authors Shay Mozes, Dekel Tsur, 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

sparse dynamic programmingordered treestree edit distancelargest common subforesttree LCS

Mathematics Subject Classification ID

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

Recommendations

• Fast Algorithms for Computing Tree LCS
• FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES
• Algorithms and Computation
• scientific article; zbMATH DE number 1998340
• scientific article; zbMATH DE number 1786462

Cites work

• scientific article; zbMATH DE number 30301 (Why is no real title available?)
• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 910858 (Why is no real title available?)
• scientific article; zbMATH DE number 1445367 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A survey on tree edit distance and related problems
• Algorithms for the Longest Common Subsequence Problem
• An Optimal Decomposition Algorithm for Tree Edit Distance
• Chaining algorithms for multiple genome comparison
• Combinatorial Pattern Matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Generalized LCS
• New algorithm for ordered tree-to-tree correction problem
• New algorithms for the LCS problem
• Preserving order in a forest in less than logarithmic time and linear space
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Simple and fast linear space computation of longest common subsequences
• Sparse dynamic programming I
• The String-to-String Correction Problem
• The Tree-to-Tree Correction Problem
• The longest common subsequence problem revisited

Cited in

(5)

• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• On almost Monge all scores matrices
• A Faster CREW PRAM Algorithm for Computing Cartesian Trees
• Fast Algorithms for Computing Tree LCS
• LSH Forest: Practical Algorithms Made Theoretical

This page was built for publication: Fast algorithms for computing tree LCS

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