Event calendar file
School of Technology and Computer Science Seminars
Introduction to Parameterized Complexity
by Mr. Bodhayan Roy (STCS, TIFR)
Friday, February 12, 2010
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 )
at Colaba Campus ( A-212 )
| Description |
For problems that are NP hard, till now we have nothing better than algorithms with exponential running times to obtain the optimal solution. 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. |
| Organised by | John Barretto |
