Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Wednesday, July 6th, 2011 Time: 1:30pm Place: DC1304         Title: How to find all centre strings? Speaker: Narges Simjour, University of Waterloo Abstract:   Finding a centre string for a set of strings has applications in computational biology. The special version of looking for a string within the minimum maximum Hamming distance from a set of equal-length input strings is called the closest string problem. The problem is NP-hard even for binary strings. The parameterized complexity of the problem has been investigated, with the optimal distance, denoted by d, being the most studied parameter. In this talk, we explain the existing fixed-parameter tractable algorithms for the problem with respect to the parameter d, and show how they can be turned into enumeration algorithms. At the end, we identify essential properties of the problem that make the enumeration parameterized tractable.