A Scalable Approximation Algorithm for Weighted Longest Common Subsequence

DOI10.1007/978-3-030-85665-6_23MaRDI QIDQ6487194zbMATH OpenFDO

Authors Jeremy Buhler, Thomas Lavastida, Kefu Lu, Benjamin Moseley

Publication date 31 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-85665-6_23

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7651110
• scientific article; zbMATH DE number 5545474
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• A new efficient algorithm for computing the longest common subsequence
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Fast linear-space computations of longest common subsequences
• Publication:4862293
• Algorithms for Computing the Longest Parameterized Common Subsequence
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings

Cites work

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

Cited in

(6)

• Finding least-weight subsequences with fewer processors
• Polynomial-time approximation algorithms for weighted LCS problem
• Polynomial-time approximation algorithms for weighted LCS problem
• Efficient parallel string comparison
• Massively parallel approximation algorithms for edit distance and longest common subsequence
• scientific article; zbMATH DE number 7651110 (Why is no real title available?)

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

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