J domination Conception et Analyse domination I
164
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
164
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- algorithmes de graphes
- universite de bergen bergen
- np-completude de sat
- algorithmes exponentiels
- temps polynomial
- generalisation de la domination
- problemes np
Publié par
Langue
Français
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
