On the approximation of longest common nonsupersequences and shortest common nonsubsequences

DOI10.1016/0304-3975(94)00257-JzbMATH Open0873.68064MaRDI QIDQ673078FDOQ673078

Authors: Louxin Zhang 

Publication date: 28 February 1997

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

Recommendations

• Maximal common subsequences and minimal common supersequences
• The shortest common nonsubsequence problem is NP-complete
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

zbMATH Keywords

binary alphabetlongest common nonsupersequence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Combined super-/substring and super-/subsequence problems
• The shortest common nonsubsequence problem is NP-complete
• Sparse long blocks and the micro-structure of the longuest common subsequences
• Title not available (Why is that?)
• Consistent subsequences and supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Title not available (Why is that?)

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

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