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

DOI10.1007/978-3-642-31265-6_11zbMATH Open1358.68112OpenAlexW206897732MaRDI QIDQ2904487FDOQ2904487

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

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

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)

Cited In (9)

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

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)