Semi-local longest common subsequences in subquadratic time
From MaRDI portal
Publication:1002102
DOI10.1016/j.jda.2008.07.001zbMath1154.68543MaRDI QIDQ1002102
Publication date: 23 February 2009
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2008.07.001
68W40: Analysis of algorithms
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
Unnamed Item, A fast algorithm for multiplying min-sum permutations, Monge properties of sequence alignment, Faster subsequence recognition in compressed strings, Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence, A substring-substring LCS data structure, On almost Monge all scores matrices, A data structure for substring-substring LCS length queries, Fast distance multiplication of unit-Monge matrices, An almost quadratic time algorithm for sparse spliced alignment, Efficient all path score computations on grid graphs, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition, Periodic String Comparison
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- A dynamic edit distance table
- A faster algorithm computing string edit distances
- Perspectives of Monge properties in optimization
- On the Common Substring Alignment Problem
- All Semi-local Longest Common Subsequences in Subquadratic Time
- Bounds on the Complexity of the Longest Common Subsequence Problem
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Algorithms on Strings, Trees and Sequences
- Incremental String Comparison
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Combinatorial Pattern Matching
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
