Periodic assignment and graph colouring

Korst, J., Aarts, E.H.L., Lenstra, J.K., & Wessels, J. (1994). Periodic assignment and graph colouring. Discrete Applied Mathematics 51 (3) 291-305. 10.1016/0166-218X(92)00036-L.

Full text not available from this repository.


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.

Item Type: Article
Uncontrolled Keywords: Periodic assignment; Graph colouring; Interval graphs; Circular-arc graphs; Periodic-interval graphs
Research Programs: Methodology of Decision Analysis (MDA)
Bibliographic Reference: Discrete Applied Mathematics; 51:291-305 [1994]
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 02:03
Last Modified: 27 Aug 2021 17:35

Actions (login required)

View Item View Item