Problème du nombre domatique
- Problème du nombre domatique
-
Problème du nombre domatique
Le problème du nombre domatique est un problème NP-complet de la théorie des graphes.
Définition
Une instance du problème du nombre domatique consiste en
- un graphe G avec un ensemble S de sommets et un ensemble A d'arcs, et
- un entier positif k inférieur ou égal au nombre de sommets dans G.
Le problème est de déterminer si le nombre domatique de G est au moins k. En d'autres termes, nous voulons savoir si S peut être partitioné en 
ensembles disjoints 
tels que chaque Si est un ensemble dominant pour G.
Complexité
Le problème du nombre domatique a été prouvé NP-complet avec une réduction depuis le problème 3SAT.
Références
- Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. A1.1: GT2, p 190. (ISBN 0-7167-1045-5)
- Garey, M. R., D. S. Johnson and R. E. Tarjan, résultats non publiés.
- Cockayne, E. J., and S. T. Hedetniemi, "Optimal domination in graphs", IEEE Trans. Circuits and Systems CAS-22, 855-857.
Catégories : Problème NP-complet | Théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Problème du nombre domatique de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Probleme du nombre domatique — Problème du nombre domatique Le problème du nombre domatique est un problème NP complet de la théorie des graphes. Définition Une instance du problème du nombre domatique consiste en un graphe G avec un ensemble S de sommets et un ensemble A d… … Wikipédia en Français
Nombre domatique — En théorie des graphes, le nombre domatique d un graphe est son nombre maximum d ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d un graphe G et d un entier naturel k, si le nombre… … Wikipédia en Français
Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La … Wikipédia en Français
Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… … Wikipédia en Français
Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
