The shortest common supersequence problem over binary alphabet is NP- complete
From MaRDI portal
Publication:1157167
DOI10.1016/0304-3975(81)90075-XzbMath0469.68049WikidataQ61067915 ScholiaQ61067915MaRDI QIDQ1157167
Esko Ukkonen, Kari-Jouko Raeihae
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Approximate periods of strings, Combined super-/substring and super-/subsequence problems, Consistent subsequences and supersequences, On the approximation of longest common nonsupersequences and shortest common nonsubsequences, Longest common subsequence problem for unoriented and cyclic strings, The consensus string problem for a metric is NP-complete, The shortest common nonsubsequence problem is NP-complete, More on the complexity of common superstring and supersequence problems, Improved heuristics and a genetic algorithm for finding short supersequences, An approximate \(A^{\ast}\) algorithm and its application to the SCS problem., About the design of oligo-chips, Scheduling tasks on a flexible manufacturing machine to minimize tool change delays, On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, Multiple genome rearrangement by swaps and by element duplications, Minimum cost multi-product flow lines
Cites Work
- Unnamed Item
- Unnamed Item
- Minimizing the Number of Evaluation Passes for Attribute Grammars
- Bounds on the Complexity of the Longest Common Subsequence Problem
- The Complexity of Some Problems on Subsequences and Supersequences
- The String-to-String Correction Problem
- The complexity of theorem-proving procedures
