PhD in Computing

Parameterized Complexity

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

iCal


Parameterized Complexity
Speaker:
Dr. Dimitrios M. Thilikos, University of Athens

Course 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.
Keywords
Course