[Back]

C. Blum, M. Djukanovic, A. Santini, H. Jiang, C. Li, F. Manya, G. Raidl:
"Solving longest common subsequence problems via a transformation to the maximum clique problem";
Computers & Operations Research, 125 (2020), 17 pages.

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.

http://dx.doi.org/10.1016/j.cor.2020.105089

https://publik.tuwien.ac.at/files/publik_293654.pdf