Computer Science – Computational Complexity
Scientific paper
2006-03-16
Computer Science
Computational Complexity
9 pages, a two-page abstract of this paper is to appear in the Proceedings of the Second IEEE International Conference on Info
Scientific paper
The 3-domatic number problem asks whether a given graph can be partitioned intothree dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors). This result improves the previous bound of 2.8805^n, which is due to Fomin, Grandoni, Pyatkin, and Stepanov. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta(G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta(G) >= 5. Our new randomized algorithm employs Schoening's approach to constraint satisfaction problems.
Riege Tobias
Rothe Jörg
Spakowski Holger
Yamamoto Masaki
No associations
LandOfFree
An Improved Exact Algorithm for the Domatic Number Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Improved Exact Algorithm for the Domatic Number Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improved Exact Algorithm for the Domatic Number Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-481061