Periodic assignment and graph colouring

J.H.M. Korst, E.H.L. Aarts, J.K. Lenstra, J. Wessels

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)
1 Downloads (Pure)

Abstract

We analyse the problem of executing periodic operations on a minimum 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. We discuss the complexity of these colouring problems in detail.
Original languageEnglish
Pages (from-to)291-305
JournalDiscrete Applied Mathematics
Volume51
Issue number3
DOIs
Publication statusPublished - 1994

Fingerprint Dive into the research topics of 'Periodic assignment and graph colouring'. Together they form a unique fingerprint.

Cite this