An improved exact algorithm for the domatic number problem

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

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

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 algorithms; randomized algorithms; exact algorithms; domatic number problem

Mathematics Subject Classification ID

68W20: Randomized algorithms

Related Items

Parameterized complexity of max-lifetime target coverage in wireless sensor networks, Inclusion/exclusion meets measure and conquer

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