J domination Conception et Analyse domination I

Mathieu Liedloff3

Description

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

Sujets

• Prague
• Verlaine

Informations

• Publié par: pefav
• Nombre de lectures: 40
• Langue: Français

Extrait

J domination Conception et Analyse (σ,%)-domination I
Algorithmes exponentiels pour une
g´en´eralisation de la domination
3Mathieu Liedloff
en collaboration avec
1 1Fedor V. Fomin Petr A. Golovach
2 3´Jan Kratochvıl Dieter Kratsch
1Universit´e de Bergen
Bergen, Norv`ege
2Universit´e Charles
Prague, R´epublique Tch`eque
3Universit´e Paul Verlaine
Metz, France
S´eminaire Visualisation et Algorithmes de Graphes, LIRMM, juin 2008
1/60J domination Conception et Analyse (σ,%)-domination I
Plan de l’expos´e
1 Introduction et motivations
2 Le probl`eme de la domination et ses variantes
3 Conception et analyse d’algorithmes exponentiels
4 Une g´en´eralisation de la domination : (σ,%)-domination
5 Conclusion
2/60J domination Conception et Analyse (σ,%)-domination I
Historique
En 1971, Cook d´emontre la NP-compl´etude deSAT [Coo71];
En 1979, Garey et Johnson [GJ79] recensent plus de 300
probl`emes NP-complets.
Juin 2008 : on ne compte plus leur nombre ...
... ils sont pr´esents dans de nombreux domaines.
Cons´equence (actuelle) la plus importante :
Aucun probl`eme NP-complet ne peut ˆetre r´esolu en temps
polynomial, sauf si P=NP.
Question ouverte depuis 30 ans!
3/60J domination Conception et Analyse (σ,%)-domination I
Historique
En 1971, Cook d´emontre la NP-compl´etude deSAT [Coo71];
En 1979, Garey et Johnson [GJ79] recensent plus de 300
probl`emes NP-complets.
Juin 2008 : on ne compte plus leur nombre ...
... ils sont pr´esents dans de nombreux domaines.
Cons´equence (actuelle) la plus importante :
Aucun probl`eme NP-complet ne peut ˆetre r´esolu en temps
polynomial, sauf si P=NP.
Question ouverte depuis 30 ans!
3/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60J domination Conception et Analyse (σ,%)-domination I
Attaques possibles
Diff´erentes attaques pour r´esoudre un tel probl`eme :
imposer des restrictions sur l’entr´ee;
chercher un algorithme d’approximation;
chercher un algorithme randomis´e;
chercher un algorithme `a param`etre fix´e;
utiliser des heuristiques;
construire un algorithme demandant un temps exponentiel.
4/60