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) Combinatorics on words (68R15) Approximation algorithms (68W25) 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)

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

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)