Periodic assignment and graph colouring

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

Research output: Book/ReportReportAcademic

48 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 that are defined on different classes of graphs, viz. interval graphs, circular-arc graphs and periodic-interval graphs. We discuss the colouring of such graphs in detail. Keywords: periodic assignment, graph colouring, interval graphs, circuJar-arc graphs, periodic-interval graphs.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages13
Publication statusPublished - 1991

Publication series

NameMemorandum COSOR
Volume9114
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Periodic assignment and graph colouring'. Together they form a unique fingerprint.

Cite this