Parameterized complexity is one of the approaches of dealing with computational intractability. The philosophy of parameterized complexity is that beyond overall input size, key secondary measurements fundamentally affect the computational complexity of problems and govern the opportunities for designing efficient algorithms. This course is an introduction to the main algorithmic techniques (like kernelization, bounded search trees, color coding, iterative compression, treewidth, and graph minors theory) for obtaining fixed-parameter tractable algorithms.
Date and time | Class|Name | Venue|short | Materials |
---|---|---|---|
19 March 17:20–20:40 |
Brief overview, kernelization, branching and bounded search trees, color coding, Lecture | ПОМИ РАН | video, files |
20 March 11:15–14:35 |
Treewidth, graph minors theorem, iterative compression, Lecture | ПОМИ РАН | video, files |