Welcome to Christophe Paul's home page
Home | Research
| Publications | Talks |
Teaching | Vitae
Avertissement : Le
matériell ci-dessous contient des notes ou des transparents
susceptibles de contenir des erreurs ou imprécisions. Les supports ne
sont pas toujours complets par rapport au contenu du cours.
Méthodes exactes : Complexité et algorithmes
paramétrés (GMIN30C)
(Master 2 Informatique, Université Montpellier 2 - 2012-2013)
- Exposé
d'introduction (Journée scientifique du LIRMM -
juin 2010)
- (1) Introduction :
paramétrisations et exemples de problèmes (slides)
- (2) Kernelization - Noyaux :
- bornes supérieures : sunflower, couronnes et conflict packing (slides)
- bornes inférieures : ou-composition, reduction paramétrés polynomiales, compositions croisée
(slides)
- (3) Algorithmes paramétrés :
- techniques algorithmiques : arbres de branchement borné, compression
itérative, algorithmes randomisés (color coding), ensembles importants (slides)
- largeur arborescente : programmation dynamique, approximation de la largeur arborescente, théorème de Courcelle (slides)
- (4) Classes de complexité
: réductions paramétrées et
W-hiérarchie (slides)
Bibliographie :
- Parameterized Complexity, R. Downey and M. Fellows, 1999.
- Invitation to Fixed-Parameter Algorithms, R. Niedermeier, 2006.
- Parameterized Complexity Theory, J. Flum and M. Grohe, 2006.
- Algorithm Design, J. Kleinberg, E. Tardos, 2005
Autres cours de master
- Introduction à la théorie de la complexité (nov. 2007)
- Méthodes polynomiales de
décomposition de graphes
- Lectures notes:
- Homeworks :
|