|
|
|
 |
|
|
|
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 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éferences
* Michael R. Garey et David S. Johnson, ''Computers and Intractability: A Guide to the Theory of NP-Completeness'', W.H. Freeman, 1979. ISBN 0-7167-1045-5}} A1.1: GT2, pg.190.
- 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 en relation : Émission de télévision britannique
|
|
|
|
|
|
|
|
|
|
