Polynomial-time approximation algorithms for weighted LCS problem

DOI10.1016/J.DAM.2015.11.011MaRDI QIDQ266804zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 7 April 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.11.011

zbMATH Keywords

longest common subsequencepolynomial-time approximation schemeweighted sequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Polynomial-time approximation algorithms for weighted LCS problem
• Weighted LCS
• Weighted LCS (extended abstract)
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Approximability of constrained LCS

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• An algorithmic framework for motif discovery problems in weighted sequences
• Approximate Matching in Weighted Sequences
• Computational and Information Science
• Computing the repetitions in a biological weighted sequence
• Polynomial-time approximation algorithms for weighted LCS problem
• Property matching and weighted matching
• String Processing and Information Retrieval
• The weighted suffix tree: an efficient data structure for handling molecular weighted sequences and its applications
• Varieties of Regularities in Weighted Sequences
• Weighted LCS

Cited in

(9)

• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Weighted LCS (extended abstract)
• Weighted LCS
• Weighted shortest common supersequence problem revisited
• Approximating LCS in Linear Time: Beating the √n Barrier
• Crochemore's partitioning on weighted strings and applications
• A multiobjective optimization algorithm for the weighted LCS
• On-line weighted pattern matching
• Polynomial-time approximation algorithms for weighted LCS problem

Describes a project that uses

Uses Software

• ClustalW

This page was built for publication: Polynomial-time approximation algorithms for weighted LCS problem

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