J domination Conception et Analyse domination I

J domination Conception et Analyse (?, %)-domination I Algorithmes exponentiels pour une generalisation de la domination Mathieu Liedloff3 en collaboration avec Fedor V. Fomin1 Petr A. Golovach1 Jan Kratochvıl2 Dieter Kratsch3 1Universite de Bergen Bergen, Norvege 2Universite Charles Prague, Republique Tcheque 3Universite Paul Verlaine Metz, France Seminaire Visualisation et Algorithmes de Graphes, LIRMM, juin 2008 1/60

• algorithmes de graphes


• universite de bergen bergen


• np-completude de sat


• algorithmes exponentiels


• temps polynomial


• generalisation de la domination


• problemes np