Polynomial-Time Approximation Algorithms for Weighted LCS Problem

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

Marek Cygan, Wojciech Rytter, Marcin Kubica, Jakub Radoszewski, 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

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

Related Items

Polynomial-time approximation algorithms for weighted LCS problem ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ Fast Average-Case Pattern Matching on Weighted Sequences ⋮ Linear-time computation of prefix table for weighted strings {\&} applications

Uses Software

• ClustalW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property matching and weighted matching
• An optimal algorithm for computing the repetitions in a word
• An Algorithmic Framework for Motif Discovery Problems in Weighted Sequences
• Varieties of Regularities in Weighted Sequences
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Approximate Matching in Weighted Sequences
• String Processing and Information Retrieval
• Computational and Information Science
• Weighted LCS