Polynomial-time approximation algorithms for weighted LCS problem

DOI10.1016/j.dam.2015.11.011zbMath1335.68304MaRDI QIDQ266804

Marek Cygan, Jakub Radoszewski, Wojciech Rytter, Marcin Kubica, Tomasz Walen

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

polynomial-time approximation scheme; longest common subsequence; weighted sequence

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

68W32: Algorithms on strings

Uses Software

• ClustalW