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.

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.

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
URI:	https://pure.iiasa.ac.at/3885

Actions (login required)

View Item