The constrained shortest common supersequence problem
From MaRDI portal
Publication:396654
DOI10.1016/j.jda.2013.03.004zbMath1334.68316MaRDI QIDQ396654
Publication date: 13 August 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.03.004
computational complexity; approximation algorithms; fixed-parameter algorithms; shortest common supersequence
68Q25: Analysis of algorithms and problem complexity
68W25: Approximation algorithms
68W32: Algorithms on strings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Variants of constrained longest common subsequence
- New efficient algorithms for the LCS and constrained LCS problems
- The constrained longest common subsequence problem
- The shortest common supersequence problem over binary alphabet is NP- complete
- Some APX-completeness results for cubic graphs
- A simple algorithm for the constrained sequence problems
- A branch-and-cut approach to the repetition-free longest common subsequence problem
- Restricted Common Superstring and Restricted Common Supersequence
- The Complexity of Some Problems on Subsequences and Supersequences
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
- ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
- Repetition-free longest common subsequence