Garey-Johnson : Différence entre versions
De AgregmathKL
(Page créée avec « Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes cl... ») |
|||
| Ligne 5 : | Ligne 5 : | ||
Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres). | Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres). | ||
Chaque problème est présenté de la manière suivante : | Chaque problème est présenté de la manière suivante : | ||
| − | + | Nom du problème | |
| − | + | Instance du problème | |
| − | + | Question (question fermée car ce sont des problèmes de décision) | |
| − | + | Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté) | |
| − | + | Commentaire (souvent des variantes du problèmes ou des choses du genre : "le problème reste NP-complet lorsque l'on restreint les instances à ...") | |
Version du 5 février 2019 à 00:00
Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes classiques comme SAT, 3SAT, VERTEX-COVER, CLIQUE, HAMILTONIAN-CIRCUIT etc. dont les réductions sont présentées directement dans le livre). Par contre, ces preuves ne sont pas très faciles à lire, il vaut peut-être mieux se référer à d'autres ouvrages pour cela.
Mais ce livre fournit une liste impressionnante de potentiels développements (qui rentrent au moins dans la leçon sur la NP-complétude) !
Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres). Chaque problème est présenté de la manière suivante :
Nom du problème Instance du problème Question (question fermée car ce sont des problèmes de décision) Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté) Commentaire (souvent des variantes du problèmes ou des choses du genre : "le problème reste NP-complet lorsque l'on restreint les instances à ...")
