Talks and Poster Presentations (with Proceedings-Entry):
M. Djukanovic, G. Raidl, C. Blum:
"A Heuristic Approach for Solving the Longest Common Square Subsequence Problem";
Talk: International Conference on Computer Aided Systems Theory (Eurocast),
Las Palmas de Gran Canaria, Spain;
- 2019-02-22; in: "EXTENDED ABSTRACTS-Computer Aided Systems Theory 2019",
IUCTC Universidad de Las Palmas de Gran Canaria,
The longest common square subsequence (LCSqS) problem,
a variant of the longest common subsequence (LCS) problem, aims at
nding a subsequence common to all input strings that is, at the same
time, a square subsequence. So far the LCSqS was solved only for two
input strings.We present a heuristic approach, based on randomized local search and a hybrid of variable neighborhood search and beam search, to solve the LCSqS for an arbitrary set of input strings. The beam search makes use of a novel heuristic estimation of the approximated expected length of a LCS to guide the search.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.