An improved exact algorithm for the domatic number problem

DOI10.1016/J.IPL.2006.08.010MaRDI QIDQ845906zbMATH OpenOpenAlexFDO

Authors Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0603060

zbMATH Keywords

randomized algorithmsexact algorithmsgraph algorithmsdomatic number problem

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: 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.

Recommendations

• Mathematical Foundations of Computer Science 2005
• An improved protocol for the exactly-N problem*
• An improved algorithm for the jump number problem
• scientific article; zbMATH DE number 764417
• An improved algorithm to compute the \(\omega\)-primality
• Graph-Theoretic Concepts in Computer Science
• An improved exact algorithm for the exact satisfiability problem
• An efficient algorithm for solving Troesch's problem
• An improved rewriting-number algorithm
• On the algorithmic complexity of some numeration-related problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• A note on the complexity of the chromatic number problem
• Algorithms and Computation
• Algorithms and Computation
• Approximating the domatic number
• Approximating theDomatic Number
• Automata, Languages and Programming
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Dominating sets and domatic number of circular arc graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Mathematical Foundations of Computer Science 2005
• New worst-case upper bounds for SAT
• STACS 2005
• The domatic number problem on some perfect graph families
• Towards a theory of domination in graphs

Cited in

(9)

• Parameterized complexity of max-lifetime target coverage in wireless sensor networks
• Approximating theDomatic Number
• Mathematical Foundations of Computer Science 2005
• Polynomial space algorithms for counting dominating sets and the domatic number
• Multi-constructor CMSA for the maximum disjoint dominating sets problem
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Domatically full Cartesian product graphs
• Approximating the domatic number
• Inclusion/exclusion meets measure and conquer

This page was built for publication: An improved exact algorithm for the domatic number problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845906)