Welcome to Christophe Paul's home page

Home | Research | Publications | Talks | Teaching | Vitae

Avertissement : Le matériel 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
(Master 2 Informatique, Université Montpellier 2)
  • (1) Introduction (3h): ce cours d'introduction offre un survol du contenu des l'ensemble des séances : difficulté d'un problème - paramétrisation - algorithmes paramétrés - kernelization (slides)
  • (2) Kernelization - Noyaux :
    • bornes supérieures (6h): sunflower, couronnes et conflict packing (slides)
suggestions d'exercices : rédaction du noyau quadratique pour cluster editing et chordal completion
    • 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)
Autre materiel
Contrôle continu 2014-2015
  • Lecture d'article : choix d'un article à lire pour le 28 novembre 2014
    • suggestion de liste d'artciles à consulter : conférence International Symposium on Parameterized and Exact Computation
    • travailler sur les versions complètes des articles
    • consignes et dates pour l'exposé : à venir en cours
    • travail en binôme possible sur deux articles liés, chacun présentera un article.
  • Compte-rendu de cours : choix du sujet pour le 28 novembre 2014
    • la note de cours (3-5 pages) devra être rédigée en Latex
    • elle devra contenir des preuves décrites en cours (au moins 2) qui seront rédigée de manière complète.
    • la note comprendra aussi le contexte et les définitions  formelles nécessaires à la description du résultat.
    • le contenu traité sera validé en cours.
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
    Bibliographie :
    M. Habib, C. Paul. A survey on modular aspects of modular decomposition. (version de travail)
    E. Gioan, C. Paul. Split decomposition and graph-labelled trees... CoRR abs/0810.1823: (2008)

      COMP 560 (SoCS, McGill, 2007): Graph algorithms and applications