Speaker: |
Bodhayan Roy Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |

Date: |
Friday, 26 Feb 2010 (all day) |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

However, if the time complexity of the algorithm has the form f(k).p(n) where k and n are output and input sizes respectively, p(n) is a polynomial over n, and f is a function depending only on k, then the algorithm performs efficiently over small values of k.

Problems having such algorithms are said to be Fixed Parameter Tractable or in the class FPT. We will study some fixed-parameter algorithms for certain common NP hard problems (this is in continuation of the talk given on 12/02/2010).