@article{(Open Science Index):https://publications.waset.org/pdf/14792,
	  title     = {Approximation Algorithm for the Shortest Approximate Common Superstring Problem},
	  author    = {A.S. Rebaï and  M. Elloumi},
	  country	= {},
	  institution	= {},
	  abstract     = {The Shortest Approximate Common Superstring
(SACS) problem is : Given a set of strings f=w1, w2, ... , wn,
where no wi is an approximate substring of wj, i ≠ j, find a shortest
string Sa, such that, every string of f is an approximate substring of
Sa. When the number of the strings n>2, the SACS problem becomes
NP-complete. In this paper, we present a greedy approximation
SACS algorithm. Our algorithm is a 1/2-approximation for the SACS
problem. It is of complexity O(n2*(l2+log(n))) in computing time,
where n is the number of the strings and l is the length of a string.
Our SACS algorithm is based on computation of the Length of the
Approximate Longest Overlap (LALO).},
	    journal   = {International Journal of Mathematical and Computational Sciences},
	  volume    = {1},
	  number    = {12},
	  year      = {2007},
	  pages     = {609 - 614},
	  ee        = {https://publications.waset.org/pdf/14792},
	  url   	= {https://publications.waset.org/vol/12},
	  bibsource = {https://publications.waset.org/},
	  issn  	= {eISSN: 1307-6892},
	  publisher = {World Academy of Science, Engineering and Technology},
	  index 	= {Open Science Index 12, 2007},
	}