AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The computation of a longest common subsequence (LCS) between two strings is a classical algorithmic problem. A generalisation of this problem, which we call semi-local LCS, asks for the LCS between a string and all substrings of another string, and/or the LCS between all prefixes of one string and all suffixes of another. This generalised problem turns out to be fundamental whenever a solution to the LCS problem has to be "glued together" from its solutions on substrings: for example, computing LCS of compressed strings; computing LCS in parallel; dynamic LCS support. The semi-local LCS problem also has surprising connections with semigroup algebra, computational geometry, planar graph algorithms, comparison networks, as well as practical applications in computational biology. The talk will discuss efficient algorithms for the semi-local LCS problem, and will survey some related results and applications.

Pawel Gawrychowski

--email hidden

passcode not visible

logged in users only