Research Article
Generalized Greedy Algorithm for Shortest Superstring
461 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
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.
Copyright © 2009–2024 ICST