Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DOMATIC NUMBER PROBLEM:
Reports tagged with domatic number problem:
TR02-068 | 10th December 2002
Tobias Riege, Jörg Rothe

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

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 computer networks, is the problem of
partitioning a given graph into a maximum number ... more >>>




ISSN 1433-8092 | Imprint