MTL780
| MTL780 | |
|---|---|
| parameterized Algorithms for Np-hard problems | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | MTL342 or COL351 or equivalent |
| Overlaps | |
MTL780 : parameterized Algorithms for Np-hard problems
[edit]Review of NP-completeness and reductions. Introduction to parameterized complexity, parameterized algorithms through bounded search trees, iterative compression, randomized methods in parameterized algorithms, dynamic programming over subsets, treewidth and parameterized algorithms for bounded treewidth graphs, algebraic techniques in parameterized complexity, Matroids and representative sets, lower bounds for parameterized algorithms based on Exponential Time Hypothesis and Strong Exponential Time Hypothesis.