GREEDY SHORTEST SUPERSTRING WITH DELAYED RANDOM CHOICE

  • Mutaz Rasmi Abu Sara, Dr. Taibah University
  • Mohammad F. J. Klaib, Dr. Taibah University
  • Masud Hasan, Prof. Taibah University
Keywords: Shortest Superstring, Greedy Algorithm, Approximation Algorithm, Approximation Ratio, Random Choice, String Overlap

Abstract

The shortest superstring problem for a given set of strings is to find a string of minimum length such that each input string is a substring of the resulting string. This problem is known to be NP-complete. A simple and popular approximation algorithm for this problem is GREEDY, which at each step merges a pair of strings that have maximum overlap. If more than one pair have maximum overlap, it takes a pair in random. In this paper, we modify GREEDY such that instead of taking a pair in random, it takes the pair for which the overlap in the next step is maximum. We analyze our algorithm and compare it with GREEDY for different types of input. We implement both the algorithms and the experimental results show that our algorithm can outperform GREEDY substantially in many cases, and in general our algorithm is same or better than GREEDY.

Published
2020-05-17
How to Cite
Abu Sara, M., Klaib, M., & Hasan, M. (2020). GREEDY SHORTEST SUPERSTRING WITH DELAYED RANDOM CHOICE. International Journal of Software Engineering and Computer Systems, 6(1), 8 - 17. Retrieved from https://journal.ump.edu.my/ijsecs/article/view/4087