Polynomial-Time Approximation Algorithms for Weighted LCS Problem

DOI10.1007/978-3-642-21458-5_38zbMath1339.68314MaRDI QIDQ3011875

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

Publication date: 29 June 2011

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21458-5_38

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

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

68W25: Approximation algorithms

68W32: Algorithms on strings

Uses Software

• ClustalW