An improved exact algorithm for the domatic number problem
From MaRDI portal
Publication:845906
DOI10.1016/J.IPL.2006.08.010zbMATH Open1185.68843arXivcs/0603060OpenAlexW2570469658MaRDI QIDQ845906FDOQ845906
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)
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.
Full work available at URL: https://arxiv.org/abs/cs/0603060
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Automata, Languages and Programming
- Approximating the domatic number
- Algorithms and Computation
- Towards a theory of domination in graphs
- Approximating theDomatic Number
- Domination, independent domination, and duality in strongly chordal graphs
- Title not available (Why is that?)
- A note on the complexity of the chromatic number problem
- Title not available (Why is that?)
- The domatic number problem on some perfect graph families
- Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
- STACS 2005
- New worst-case upper bounds for SAT
- Dominating sets and domatic number of circular arc graphs
- Algorithms and Computation
- Mathematical Foundations of Computer Science 2005
Cited In (8)
- Parameterized complexity of max-lifetime target coverage in wireless sensor networks
- Mathematical Foundations of Computer Science 2005
- Approximating theDomatic Number
- 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
- 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)
