Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009, Revised Papers, Part 2

Research Article

Generalized Greedy Algorithm for Shortest Superstring

Download46 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-02469-6_32,
        author={Zhengjun Cao and Lihua Liu and Olivier Markowitch},
        title={Generalized Greedy Algorithm for Shortest Superstring},
        proceedings={Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009, Revised Papers, Part 2},
        proceedings_a={COMPLEX PART 2},
        year={2012},
        month={5},
        keywords={greedy algorithm shortest superstring optimal set},
        doi={10.1007/978-3-642-02469-6_32}
    }
    
  • Zhengjun Cao
    Lihua Liu
    Olivier Markowitch
    Year: 2012
    Generalized Greedy Algorithm for Shortest Superstring
    COMPLEX PART 2
    Springer
    DOI: 10.1007/978-3-642-02469-6_32
Zhengjun Cao,*, Lihua Liu1, Olivier Markowitch2
  • 1: Shanghai Maritime University
  • 2: Université Libre de Bruxelles
*Contact email: caoamss@gmail.com

Abstract

In the primitive greedy algorithm for shortest superstring, if a pair of strings with maximum overlap picked out, they are subsequently merged. In this paper, we introduce the concept of optimal set and generalize the primitive greedy algorithm. The generalized algorithm can be reduced to the primitive greedy algorithm if the relative optimal set is empty. Consequently, the new algorithm achieves a better bound at the expense of cost. But the cost is acceptable in practice.