Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Solving longest common subsequence problems via a transformation to the maximum clique problem

Abstract : Longest common subsequence problems find various applications in bioinformatics, data compression and text editing, just to name a few. Even though numerous heuristic approaches were published in the related literature for many of the considered problem variants during the last decades, solving these problems to optimality remains an important challenge. This is particularly the case when the number and the length of the input strings grows. In this work we define a new way to transform instances of the classical longest common subsequence problem and of some of its variants into instances of the maximum clique problem. Moreover, we propose a technique to reduce the size of the resulting graphs. Finally, a comprehensive experimental evaluation using recent exact and heuristic maximum clique solvers is presented. Numerous, so-far unsolved problem instances from benchmark sets taken from the literature were solved to optimality in this way. (C) 2020 Elsevier Ltd. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636411
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:07
Dernière modification le : lundi 11 avril 2022 - 03:31:05

Identifiants

Collections

Citation

Christian Blum, Marko Djukanovic, Alberto Santini, Hua Jiang, Chu-Min Li, et al.. Solving longest common subsequence problems via a transformation to the maximum clique problem. Computers & Operations Research, 2021, 125, ⟨10.1016/j.cor.2020.105089⟩. ⟨hal-03636411⟩

Partager

Métriques

Consultations de la notice

30