Polynomial-time approximation algorithms for weighted LCS problem

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

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

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 schemelongest common subsequenceweighted sequence

Mathematics Subject Classification ID

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

Related Items (3)

Crochemore's partitioning on weighted strings and applications ⋮ On-line weighted pattern matching ⋮ Unnamed Item

Uses Software

• ClustalW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property matching and weighted matching
• Polynomial-Time Approximation Algorithms for Weighted LCS Problem
• An Algorithmic Framework for Motif Discovery Problems in Weighted Sequences
• Varieties of Regularities in Weighted Sequences
• Algorithms on Strings, Trees and Sequences
• Approximate Matching in Weighted Sequences
• String Processing and Information Retrieval
• Computational and Information Science
• Weighted LCS

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