The shortest common nonsubsequence problem is NP-complete

DOI10.1016/0304-3975(93)90200-DzbMath0776.68061OpenAlexW2037691423MaRDI QIDQ1208726

S. Singh

Publication date: 16 May 1993

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

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90200-d

zbMATH Keywords

combinatorial optimizationNP-completenessstrings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (5)

Combined super-/substring and super-/subsequence problems ⋮ Consistent subsequences and supersequences ⋮ On the approximation of longest common nonsupersequences and shortest common nonsubsequences ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ On trace inclusion optimization problems

Cites Work

• Unnamed Item
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• The shortest common supersequence problem over binary alphabet is NP- complete
• The Complexity of Some Problems on Subsequences and Supersequences

This page was built for publication: The shortest common nonsubsequence problem is NP-complete