Science Fair Project Encyclopedia
Domatic number problem
The domatic number problem is an NP-complete problem in graph theory.
Definition
An instance of the domatic number problem consists of:
- a graph G with a set V of vertices and a set E of edges, and
- a positive integer K smaller than or equal to the number of vertices in G.
The problem is to determine whether the domatic number of G is at least K. In other words, we want to know if V can be partitioned into k ≤K disjoint sets V1, V2,...,Vk such that each Vi is a dominating set for G.
NP-complete
The domatic number problem is proven to be NP-complete by a reduction from the 3-Satisfiability problem.
References
- Garey, M. R. and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979.
- Garey, M. R., D. S. Johnson and R. E. Tarjan, unpublished results.
- Cockayne, E. J., and S. T. Hedetniemi, "Optimal domination in graphs", IEEE Trans. Circuits and Systems CAS-22, 855-857.
Last updated: 05-29-2005 09:11:47
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details