Generalized Greedy Algorithm for Shortest Superstring

Zhengjun Cao; Lihua Liu; Olivier Markowitch

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

Download

443 downloads

Cite: BibTeX Plain Text

@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 Liu¹, Olivier Markowitch²

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.

Keywords: greedy algorithm shortest superstring optimal set

Published: 2012-05-11

: http://dx.doi.org/10.1007/978-3-642-02469-6_32