Talks and Poster Presentations (with Proceedings-Entry):

M. Djukanovic, C. Berger, G. Raidl, C. Blum:
"On Solving a Generalized Constrained Longest Common Subsequence Problem";
Talk: International Conference on Optimization and Applications, Moscow, Russia; 2020-09-28 - 2020-10-02; in: "International Conference on Optimization and Applications-OPTIMA2020", LNCS / Springer, 12422 (2020), ISBN: 978-3-030-62866-6; 55 - 70.

English abstract:
Given a set of two input strings and a pattern string, the
constrained longest common subsequence problem deals with finding a
longest string that is a subsequence of both input strings and that contains
the given pattern string as a subsequence. This problem has various
applications, especially in computational biology. In this work we consider
the NP-hard case of the problem in which more than two input
strings are given. First, we adapt an existing A

search from two input
strings to an arbitrary number m of input strings (m ≥ 2). With the aim
of tackling large problem instances approximately, we additionally propose
a greedy heuristic and a beam search. All three algorithms are compared
to an existing approximation algorithm from the literature. Beam
search turns out to be the best heuristic approach, matching almost all
optimal solutions obtained by A

search for rather small instances.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.