Garey-Johnson

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 (des variantes du problèmes ou des choses du genre : "ça reste NP-complet même quand on restreint les instances à ...")

David X