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

doi:10.1016/0304-3975(81)90075-X

Theoretical Computer Science

Volume 16, Issue 2, 1981, Pages 187-198

https://doi.org/10.1016/0304-3975(81)90075-X Get rights and content

Under an Elsevier user license

open archive

Abstract

We consider the complexity of the Shortest Common Supersequence (SCS) problem, i.e. the problem of finding for finite strings S₁, S₂,…, S_u a shortest string S such that every S_i can be obtained by deleting zero or more elements from S. The SCS problem is shown to be NP-complete for strings over an alphabet of size ⩾ 2.

Cited by (0)

^∗: The work of this author was supported by the Academy of Finland.