Set packing

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le problème de set packing est un problème d'optimisation combinatoire NP-complet. Il peut être considéré comme une version particulière du problème du sac à dos multidimensionnel où les poids des objets sont égaux à 0 ou 1 et où les capacités du sac sont toutes égales à 1.

v · m Les 21 problèmes NP-complets de Karp
SAT 3-SAT Problème de la clique Partition en cliques Problème de partition Set packing (empaquetage d'ensemble) Couverture par sommets Couverture par ensembles Couverture exacte Feedback arc set Feedback vertex set Cycle hamiltonien Circuit hamiltonien Optimisation linéaire en nombres entiers Coloration de graphe Appariement à 3 dimensions Arbre de Steiner Ensemble intersectant Sac à dos Séquençage de tâches Problème de la coupe maximum

v · m

Les 21 problèmes NP-complets de Karp