2005/06/24 by Tobias Riege, Jörg Rothe, Riege, Tobias +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.2.2 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0506090
20 pages, 1 figure
arxiv created 2005/06/24 · openalex publication_date 2005/06/24 · arxiv updated 2009/12/01 · openalex created_date 2016/09/23 · openalex updated_date 2026/07/28
The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3n, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416n. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.