The shortest common supersequence problem over binary alphabet is NP- complete

DOI10.1016/0304-3975(81)90075-XzbMath0469.68049OpenAlexW2053393747WikidataQ61067915 ScholiaQ61067915MaRDI QIDQ1157167

Esko Ukkonen, Kari-Jouko Raeihae

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90075-x

zbMATH Keywords

NP-completenesssemantic attribute evaluation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semantics in the theory of computing (68Q55)

Related Items (32)

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems ⋮ A beam search for the shortest common supersequence problem guided by an approximate expected length calculation ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Combined super-/substring and super-/subsequence problems ⋮ The consensus string problem for a metric is NP-complete ⋮ Compact Flow Diagrams for State Sequences ⋮ Improved heuristics and a genetic algorithm for finding short supersequences ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ The constrained shortest common supersequence problem ⋮ Variants of constrained longest common subsequence ⋮ An approximate \(A^{\ast}\) algorithm and its application to the SCS problem. ⋮ String Covering: A Survey ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ The complexity of flood-filling games on graphs ⋮ Conjunctive query containment over trees using schema information ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ Consistent subsequences and supersequences ⋮ On the approximation of longest common nonsupersequences and shortest common nonsubsequences ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ Feasibility recovery for the unit-capacity constrained permutation problem ⋮ The unit-capacity constrained permutation problem ⋮ Minimum cost multi-product flow lines ⋮ The complexity of flood filling games ⋮ Conjunctive query containment over trees ⋮ The shortest common nonsubsequence problem is NP-complete ⋮ About the design of oligo-chips ⋮ Scheduling tasks on a flexible manufacturing machine to minimize tool change delays ⋮ Approximate periods of strings ⋮ Tractability and hardness of flood-filling games on trees ⋮ More on the complexity of common superstring and supersequence problems

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

This page was built for publication: The shortest common supersequence problem over binary alphabet is NP- complete