Fast algorithms for computing tree LCS

DOI10.1016/J.TCS.2009.07.011zbMATH Open1187.68684OpenAlexW2069957592WikidataQ60143026 ScholiaQ60143026MaRDI QIDQ732018FDOQ732018

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• 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)