Algoritmos de aproximacao para Shortest Superstring(SS) 
   (Paper: Blum, Jiang, Li, Tromp e Yannakakis) 

                  Eduardo C. Xavier 
                  Sala 96  13:00hs 
O problema SS pode ser definido como: Dado um conjunto S de strings 
temos que encontrar a menor string X que seja superstring de todas 
strings do conjunto S, ou seja, para toda string s de S, s e substring 
de X. Este problema e NP-dificil e tem varias aplicacoes praticas como 
reajuntamento de fragmentos de DNA. Mostraremos no seminario dois 
algoritmos para o problema. O primeiro e uma 4 aproximacao e o segundo 
uma 3 aproximacao.