Periodic assignment and graph colouring

Korst J, Aarts EHL, Lenstra JK, & Wessels J (1994). Periodic assignment and graph colouring. Discrete Applied Mathematics 51 (3): 291-305. DOI: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: 24 Aug 2016 12:35
URI: http://pure.iiasa.ac.at/3885

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313