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 l  \leq k ensembles disjoints S_1, S_2, \dots, S_l 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.
Ce document provient de « Probl%C3%A8me du nombre domatique ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”