Periodic assignment and graph colouring
type: Item
instance of: scholarly article
title: Periodic assignment and graph colouring
zbMATH Open document ID: 0807.05030
DOI: 10.1016/0166-218X(92)00036-L
author: Jan Karel Lenstra
author: J. Korst
author: E. Aarts
author: J. Wessels
published in: Discrete Applied Mathematics
publication date: 1994-07-31T00:00:00Z
review text: This paper deals with the problem of assigning periodic operations to a minimum number of identical processors under different constraints. The periodic assignment problem naturally arises in such diverse areas as real-time processing, vehicle scheduling and compiler design. The authors consider two different models of scheduling: (1) unconstrained periodic assignment, where different executions of an operation may be assigned to different processors, and (2) constrained periodic assignment, where all executions of an operation have to be assigned to the same processor. They show that the latter case leads to an NP-hard problem of coloring circular-arc graphs and periodic-interval graphs. These two classes of graphs include interval graphs. The authors then prove that two heuristics for coloring circular-arc graphs require less than twice the minimum number of colors. Surprisingly, each general graph is a periodic-interval graph, so no such polynomial algorithm for periodic-interval graph is likely to exist.
reviewed by: Marek Kubale
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 612414
zbMATH Keywords: periodic assignment
zbMATH Keywords: NP-hard problem
zbMATH Keywords: coloring
zbMATH Keywords: circular-arc graphs
zbMATH Keywords: periodic-interval graphs
zbMATH Keywords: interval graphs
MaRDI profile type: Publication
cites work: Q3361873
cites work: A better performance guarantee for approximate graph coloring
cites work: Q3097395
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: On the complexity of computing the measure of ∪[a i ,b i ]
cites work: Incidence matrices and interval graphs
cites work: Q4198056
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Algorithms on circular-arc graphs
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: An Optimal Solution for the Channel-Assignment Problem
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q4142699
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Q4130999
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: On the complexity of fixed-priority scheduling of periodic, real-time tasks
cites work: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
cites work: The Lattice Point Covering Theorem for Rectangles
cites work: Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: Technical Note—Optimal Scheduling of Periodic Activities
cites work: An \(0(n^{1.5})\) algorithm to color proper circular arcs
cites work: An O(qn) algorithm to q-color a proper family of circular arcs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
description: scientific article; zbMATH DE number 612414