### Thread: Shortest Covering String Problem

1. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
3
Rep Power
0

#### Shortest Covering String Problem

shortest Covering String problem
Input: Finite alphabet SIGMA of t symbols;
collection C={SIGMA1,SIGMA2,...,SIGMAn} of subsets of SIGMA
Output: Find a string w, (sequence of symbols) over SIGMA such that |w| is minimum
and for each 1< =i< =n, all of the symbols in SIGMAi appear
in a consecutive block of |SIGMAi| symbols in the string w.
Last edited by Vigilant; August 27th, 2003 at 02:48 AM.
2. No Profile Picture
epl
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2001
Location
Dublin
Posts
413
Rep Power
18
with no concern about efficiency i would do the following:

generate all strings ww such that each is based on a concatenation of each of the SIGMAi's, with all possible orders of the individual elements / characters within each SIGMAi covered.

AC ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D

then go to the next permutation for SIGMA1

CA ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
then
AC ABEG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC ABGE BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC AEBG BCDEFG BCDFG CDFG ADFG ABDEG ABDG D
AC AEGB BCDEFG BCDFG CDFG ADFG ABDEG ABDG D

etc.

then clear each ww string by removing all but one of any sequence of consecutive characters. given a permutations routine you will be able to work through the possibilities as you would in any find-the-minimum type routine - with no need to keep more than one of the ww strings in memory at a time.
3. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
3
Rep Power
0
i have found the solution the shortest covering string problem.
it is np
Last edited by Vigilant; August 27th, 2003 at 02:45 AM.
4. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
3
Rep Power
0
i have found the solution to the shortest covering string problem