| Article ID: | iaor19951083 |
| Country: | Netherlands |
| Volume: | 51 |
| Issue: | 3 |
| Start Page Number: | 291 |
| End Page Number: | 305 |
| Publication Date: | Jul 1994 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Wessels Jaap, Lenstra Jan Karel, Aarts Emile, Korst Jan |
| Keywords: | graph colouring |
The authors analyse the problem of executing periodic operations on a minimim number of identical processors under different constraints. The analysis is based on a reformulation of the problem in terms of graph colouring. It is shown that different constraints result in colouring problems defined on different classes of graphs, viz. interval graphs, circular-arc graphs and periodic-interval graphs. The authors discuss the complexity of these colouring problems in detail.