15 citations · 15 across the 3 of their papers we have counts for
3 papers
cs.CC2006
An Improved Exact Algorithm for the Domatic Number Problem
Tobias Riege, Jörg Rothe, Holger Spakowski +1
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…
cs.CC2005
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem
Tobias Riege, Jörg Rothe
The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the verte…
cs.CC2002★ 15 cited
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
Tobias Riege, Jörg Rothe
We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of…