Vortrag von Prof. Dr. Dominique de Werra (Ecole
Polytechnique Fédérale de Lausanne)
Graph coloring models are often unable to provide an
efficient help in the solution of real timetabling or scheduling
problems; the reason is that there are many additional requirements
which have to be introduced. In this talk we will consider some of
these and in particular the existence of feasible sets of colors.
These "local" requirements will be combined with "global"
constraints (like bounds on the cardinalities of the color glasses)
and we discuss complexity of this problem. Applications in
timetabling as well as in robotics will be given.