An improved exact algorithm for the domatic number problem

DOI10.1016/j.ipl.2006.08.010zbMath1185.68843arXivcs/0603060OpenAlexW2570469658MaRDI QIDQ845906

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

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

graph algorithmsrandomized algorithmsexact algorithmsdomatic number problem

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (4)

Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ Inclusion/exclusion meets measure and conquer ⋮ Domatically full Cartesian product graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Dominating sets and domatic number of circular arc graphs
• A note on the complexity of the chromatic number problem
• The domatic number problem on some perfect graph families
• New worst-case upper bounds for SAT
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Approximating the domatic number
• Towards a theory of domination in graphs
• Approximating theDomatic Number
• Mathematical Foundations of Computer Science 2005
• STACS 2005
• Automata, Languages and Programming
• Algorithms and Computation
• Algorithms and Computation

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