Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

A NP-complete problem

SpeakerDominique de Werra

Co-authorsC. Bentz, M.C. Costa, C. Picouleau and B. Ries

The basic image reconstruction problem in discrete tomography consists in assigning some color for every pixel of a rectangular array in such a way that requirements on the number of occurrences of each color in the rows and columns are satisfied.

This can be modelled as a vertex coloring problem in a graph with additional constraints.

In a similar way, chromatic scheduling considers applications of coloring models to various types of scheduling problems; here also additional requirements have to be introduced in order to capture the essential constraints of the scheduling problem.

Here we shall be concerned with graph coloring models where, in addition to the usual requirements occurring in coloring problems, we will have a collection P of chains Pi of the associated graph and it will be required that in each Pi color j occurs exactly hij times, where the hij are given integers.

We will examine special cases of graphs like trees, cacti and bipartite graphs. Polynomially solvable cases will be identified and general complexity results will be given. We will also relax some assumptions on colorings and study cases where the colorings need not be proper. The case of edge coloring (often used in basic timetabling models) will also be investigated. Open questions will finally be raised in relation with applications.

Keywordschromatic scheduling, discrete tomography, image reconstruction, graph coloring, complexity