Inroduction influence des parametres Problemes algorithmes parametres Complexite parametree et approximation

Inroduction - influence des parametres Problemes, algorithmes parametres Complexite parametree et approximation Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345) Christophe PAUL (CNRS - LIRMM) November 4, 2008 Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)

• complexite parametree


• inroduction - influence des parametres problemes


• parametre specifique au probleme


• algorithmes parametres


• fixed-parameter algorithms


• croissance exponentielle du temps de calcul