Title :
Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
Author :
Riege, Tobias ; Rothe, Jorg
Author_Institution :
Inst. fur Informatik, Heinrich-Heine-Univ. Dusseldorf, Germany
Abstract :
The domatic number problem, DNP, arises in the area of computer networks, e.g., in the task of allocating resources in a computer network or in the task of transmitting messages in a communication network. This paper describes the complexity of the exact domatic number problem and of the exact conveyor flow shop problem.
Keywords :
computational complexity; flow shop scheduling; graph colouring; minimisation; resource allocation; DNP; computer network; conveyor flow shop problem; domatic number problem; resources allocation; Communication networks; Computational complexity; Computer networks; Polynomials; Resource management; Turing machines;
Conference_Titel :
Information and Communication Technologies: From Theory to Applications, 2004. Proceedings. 2004 International Conference on
Print_ISBN :
0-7803-8482-2
DOI :
10.1109/ICTTA.2004.1307935
