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-17
- 2019-02-22; in: "EXTENDED ABSTRACTS-Computer Aided Systems Theory 2019",
IUCTC Universidad de Las Palmas de Gran Canaria,
(2019),
ISBN: 978-84-09-09208-6;
120
- 122.
English abstract:
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:
https://publik.tuwien.ac.at/files/publik_280651.pdf
Created from the Publication Database of the Vienna University of Technology.