A hybrid genetic algorithm for the repetition free longest common subsequence problem

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique.

Original languageEnglish
Pages (from-to)644-649
Number of pages6
JournalOperations Research Letters
Volume41
Issue number6
DOIs
Publication statusPublished - 1 Oct 2013

Keywords

  • Estimation of distribution algorithms
  • Genetic algorithms
  • Heuristics
  • Repetition free longest common subsequence

Fingerprint Dive into the research topics of 'A hybrid genetic algorithm for the repetition free longest common subsequence problem'. Together they form a unique fingerprint.

  • Cite this