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

DOI10.1016/0304-3975(81)90075-XMaRDI QIDQ1157167zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Minimizing the Number of Evaluation Passes for Attribute Grammars
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The complexity of theorem-proving procedures

Cited in

(33)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1157167)