A Scalable Approximation Algorithm for Weighted Longest Common Subsequence

DOI10.1007/978-3-030-85665-6_23zbMath1512.68464MaRDI QIDQ6487194

Kefu Lu, Jeremy Buhler, Benjamin Moseley, Thomas Lavastida

Publication date: 31 March 2022

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monge properties of sequence alignment
• Semi-local string comparison: algorithmic techniques and applications
• Geometric applications of a matrix-searching algorithm
• A faster algorithm computing string edit distances
• Fast distance multiplication of unit-Monge matrices
• An all-substrings common subsequence algorithm
• A coarse-grained parallel algorithm for the all-substrings longest common subsequence problem
• Efficient Parallel Algorithms for String Editing and Related Problems
• Efficient Longest Common Subsequence Computation Using Bulk-Synchronous Parallelism
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Efficient massively parallel methods for dynamic programming

This page was built for publication: A Scalable Approximation Algorithm for Weighted Longest Common Subsequence