Added to Favorites

Popular Searches

Definitions

Nearby Words

This shortest common supersequence problem is closely related to the longest common subsequence problem. Given two sequences X = < x_{1},...,x_{m} > and Y = < y_{1},...,y_{n} >, a sequence U = < u_{1},...,u_{k} > is a common supersequence of X and Y if U is a supersequence of both X and Y. ## References

## External links

The shortest common supersequence (scs) is a common supersequence of minimal length. In the shortest common supersequence problem, the two sequences X and Y are given and the task is to find a shortest possible common supersequence of these sequences. In general, the scs is not unique.

For two input sequences, an scs can be formed from an lcs easily. For example, if X$[1..m]\; =\; abcbdab$ and Y$[1..n]\; =\; bdcaba$, the lcs is Z$[1..r]\; =\; bcba$. By inserting the non-lcs symbols while preserving the symbol order, we get the scs: U$[1..t]\; =\; abdcabdab$.

It is quite clear that $r\; +\; t\; =\; m\; +\; n$ for two input sequences. However, for three or more input sequences this does not hold. Note also, that the lcs and the scs problems are not dual problems.

- Michael R. Garey and David S. Johnson (1979).
*Computers and Intractability: A Guide to the Theory of NP-Completeness*. W.H. Freeman. ISBN 0-7167-1045-5. A4.2: SR8, pg.228.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday April 19, 2008 at 08:06:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday April 19, 2008 at 08:06:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.