Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
From MaRDI portal
Publication:2904487
DOI10.1007/978-3-642-31265-6_11zbMath1358.68112OpenAlexW206897732MaRDI QIDQ2904487
Stéphane Vialette, Pedro J. Tejada, Laurent Bulteau, Guillaume Blin, Ming-Hui 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
Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items (4)
Hardness and approximation of multiple sequence alignment with column score ⋮ Unnamed Item ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Graph Logics with Rational Relations
This page was built for publication: Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
