![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Alexander Tiskin, Department of Computer Science, University of Warwick
Wednesday 31 October 2012, 14:15-15:15
Semi-local string comparison
- đ¤ Speaker: Alexander Tiskin, Department of Computer Science, University of Warwick
- đ Date & Time: Wednesday 31 October 2012, 14:15 - 15:15
- đ Venue: Lecture Theatre 1, Computer Laboratory
Abstract
The computation of a longest common subsequence (LCS) between two strings is a classical algorithmic problem. Some applications require a generalisation of this problem, which we call semi-local LCS . It 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. Apart from an important role that this generalised problem plays in string algorithms, it turns out to have surprising connections with semigroup algebra, computational geometry, planar graph algorithms, comparison networks, as well as practical applications in computational biology. The talk will present an efficient solution for the semi-local LCS problem, and will survey some related results and applications. Among those are dynamic LCS support; fast clique computation in special graphs; fast comparison of compressed strings; parallel string algorithms.
Series This talk is part of the Wednesday Seminars - Department of Computer Science and Technology series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Chris Davis' list
- computer science
- Department of Computer Science and Technology talks and seminars
- Graduate-Seminars
- Guy Emerson's list
- Interested Talks
- Lecture Theatre 1, Computer Laboratory
- Martin's interesting talks
- School of Technology
- se393's list
- Trust & Technology Initiative - interesting events
- Wednesday Seminars - Department of Computer Science and Technology
- yk449
Note: Ex-directory lists are not shown.