Periodic assignment and graph colouring

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

doi:10.1016/0166-218X(92)00036-L

Periodic assignment and graph colouring

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

Research output: Contribution to journal › Article › Academic › peer-review

13 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 language	English
Pages (from-to)	291-305
Journal	Discrete Applied Mathematics
Volume	51
Issue number	3
DOIs	https://doi.org/10.1016/0166-218X(92)00036-L
Publication status	Published - 1994

Access to Document

10.1016/0166-218X(92)00036-L

Cite this

@article{4e797dca3f9e4b0c9d6136ee53a5c6b0,

title = "Periodic assignment and graph colouring",

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.",

author = "J.H.M. Korst and E.H.L. Aarts and J.K. Lenstra and J. Wessels",

year = "1994",

doi = "10.1016/0166-218X(92)00036-L",

language = "English",

volume = "51",

pages = "291--305",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "3",

}

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 -

Periodic assignment and graph colouring

Abstract

Access to Document

Fingerprint

Cite this