An Exact 2.9416^n Algorithm for the Three Domatic Number Problem
| dc.creator | Riege, Tobias | |
| dc.creator | Rothe, Jörg | |
| dc.date | 2005-06-24 | |
| dc.date.accessioned | 2026-07-07T03:23:10Z | |
| dc.date.available | 2026-07-07T03:23:10Z | |
| dc.description | 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 3^n, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416^n. 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. | |
| dc.description | 20 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0506090 | |
| dc.identifier | http://arxiv.org/abs/cs/0506090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32839 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2 | |
| dc.title | An Exact 2.9416^n Algorithm for the Three Domatic Number Problem | |
| dc.type | text |