Probleme du nombre domatique
- 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'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 Probleme du nombre domatique de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
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… … 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
