An Improved Exact Algorithm for the Domatic Number Problem

Simple item page
dc.creatorRiege, Tobias
dc.creatorRothe, Jörg
dc.creatorSpakowski, Holger
dc.creatorYamamoto, Masaki
dc.date2006-03-16
dc.date.accessioned2026-07-07T07:05:51Z
dc.date.available2026-07-07T07:05:51Z
dc.descriptionThe 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.
dc.description9 pages, a two-page abstract of this paper is to appear in the Proceedings of the Second IEEE International Conference on Information & Communication Technologies: From Theory to Applications, April 2006
dc.identifierhttps://arxiv.org/abs/cs/0603060
dc.identifierhttp://arxiv.org/abs/cs/0603060
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/109812
dc.subjectComputational Complexity
dc.subjectF.2.2
dc.titleAn Improved Exact Algorithm for the Domatic Number Problem
dc.typetext

Files

Collections

arXiv