Hardness of longest common subsequence for sequences with bounded run-lengths

DOI10.1007/978-3-642-31265-6_11MaRDI QIDQ2904487zbMATH OpenOpenAlexFDO

Authors Guillaume Blin, Laurent Bulteau, Pedro J. Tejada, Stéphane Vialette, Minghui Jiang

Publication date 14 August 2012

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

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00683311/file/hal.pdf

Mathematics Subject Classification ID

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

Recommendations

• Constrained LCS: Hardness and Approximation
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• Combinatorial Pattern Matching
• On the longest common rigid subsequence problem
• Longest common subsequence problem for unoriented and cyclic strings

Cited in

(9)

• Listing center strings under the edit distance metric
• Graph logics with rational relations: the role of word combinatorics
• The generalized definitions of the two-dimensional largest common substructure problems
• Hardness and approximation of multiple sequence alignment with column score
• On the longest common rigid subsequence problem
• Exemplar Longest Common Subsequence
• Longest common subsequence problem for unoriented and cyclic strings
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)

This page was built for publication: Hardness of longest common subsequence for sequences with bounded run-lengths

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