Preassignment requirements in chromatic scheduling

✍ Scribed by D. de Werra; N.V.R. Mahadev

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 615 KB
• Volume: 76
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)82776-x

✦ Synopsis

In open shop and class-teacher timetabling problems preassignment requirements are often present; they are represented by precolorings in the graphs associated with the models. We consider the problem of extending a precoloring to an edge k-coloring of the whole graph (where k is fixed) and we describe some polynomially solvable cases of this problem which is generally NP-complete. A model with cost is given and we show that for trees it can be solved in polynomial time.