Periodic assignment and graph colouring

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

Research output: Contribution to journalArticleScientificpeer-review

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
Number of pages15
JournalDiscrete Applied Mathematics
Volume51
Issue number3
DOIs
Publication statusPublished - 1994
Externally publishedYes

Fingerprint

Graph Coloring
Coloring
Assignment
Interval Graphs
Colouring
Circular-arc Graphs
Reformulation
Graph in graph theory

Cite this

Korst, J.H.M. ; Aarts, E.H.L. ; Lenstra, J.K. ; Wessels, J. / Periodic assignment and graph colouring. In: Discrete Applied Mathematics. 1994 ; Vol. 51, No. 3. pp. 291-305.
@article{7ad08fb4096844fdb3f134bba919ce86,
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",
number = "3",

}

Periodic assignment and graph colouring. / Korst, J.H.M.; Aarts, E.H.L.; Lenstra, J.K.; Wessels, J.

In: Discrete Applied Mathematics, Vol. 51, No. 3, 1994, p. 291-305.

Research output: Contribution to journalArticleScientificpeer-review

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

VL - 51

SP - 291

EP - 305

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 3

ER -