On the approximation of longest common nonsupersequences and shortest common nonsubsequences

DOI10.1016/0304-3975(94)00257-JzbMath0873.68064MaRDI QIDQ673078

Louxin Zhang

Publication date: 28 February 1997

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

zbMATH Keywords

binary alphabetlongest common nonsupersequence

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Combined super-/substring and super-/subsequence problems ⋮ Consistent subsequences and supersequences

Cites Work

• Unnamed Item
• On the complexity of learning strings and sequences
• The shortest common supersequence problem over binary alphabet is NP- complete
• Theory and algorithms for plan merging
• The shortest common nonsubsequence problem is NP-complete
• The Complexity of Some Problems on Subsequences and Supersequences
• String Noninclusion Optimization Problems
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

This page was built for publication: On the approximation of longest common nonsupersequences and shortest common nonsubsequences