TY - JOUR
T1 - Periodic assignment and graph colouring
AU - Korst, J.H.M.
AU - Aarts, E.H.L.
AU - Lenstra, J.K.
AU - Wessels, J.
PY - 1994
Y1 - 1994
N2 - 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.
AB - 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.
U2 - 10.1016/0166-218X(92)00036-L
DO - 10.1016/0166-218X(92)00036-L
M3 - Article
SN - 0166-218X
VL - 51
SP - 291
EP - 305
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -