

Bristol Algorithms Days 2010 Feasibility Workshop
15  16 February 2010

Strings, Points, Braids and Genes
Alexander Tiskin
The longest common subsequence (LCS) problem
is a classical problem in computer science.
The semilocal LCS problem is a generalisation of the LCS problem,
arising naturally in the context of string comparison.
Apart from playing an important role in string algorithms,
this problem turns out to have surprising connections
with computational geometry, algebra, graph theory,
as well as applications in computational molecular biology.
The talk gives a survey of recent results that expose these connections.
We conclude that semilocal string comparison
is a fascinating problem and a powerful algorithmic technique,
which unifies and improves on a number of previous approaches.
Back
 