Parameterized Complexity
PhD program in Computing Course
- https://computing.phd.upc.edu/en/esdeveniments/parameterized-complexity
- Parameterized Complexity
- 2015-11-23T10:00:00+01:00
- 2015-11-23T11:00:00+01:00
- PhD program in Computing Course
When
Nov 23, 2015 from 10:00 AM to 11:00 AM (Europe/Madrid / UTC100)
Where
Room S208 Omega Building
Add event to calendar
Parameterized Complexity
Speaker:
Dr. Dimitrios M. Thilikos, University of AthensCourse outline
1. Introduction and basic definitions
- Why parameterized complexity?
- The idea of parameterization
- The class FPT and FPT-reductions
- The classes para-NP, XP
- The classes W[P] and W[SAT]
- The classes W[1], W[2],. . .
- Sub-exponential time hypothesis
3. FPT algorithm design
- Bounded search trees
- Greedy localization
- Color coding
- Tree and branch decompositions
- Graph minors
- Courcelle's theorem
- Kernelization
- Reduction rules
6. Faster FPT-algorithms
- Subexponential FPT
- Bidimensionality
- Catalan structures
- Open problems
The course is supported by "programa de movilidad de profesores para programas de doctorado con mención de calidad 07-08" and it is open to any interested person.
Share: