Periodic assignment and graph colouring

DOI10.1016/0166-218X(92)00036-LzbMATH Open0807.05030MaRDI QIDQ1329789FDOQ1329789

Authors: Jan Karel Lenstra, J. Korst, E. Aarts, J. Wessels 

Publication date: 31 July 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• An approximation result for a periodic allocation problem
• Precoloring extension. I: Interval graphs
• Chromatic scheduling and frequency assignment
• A study of the cyclic scheduling problem on parallel processors
• Mutual exclusion scheduling with interval graphs or related classes. I

zbMATH Keywords

interval graphscircular-arc graphscoloringNP-hard problemperiodic assignmentperiodic-interval graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Graph theory with applications
• On the complexity of fixed-priority scheduling of periodic, real-time tasks
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Representation of a finite graph by a set of intervals on the real line
• A Characterization of Comparability Graphs and of Interval Graphs
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An Optimal Solution for the Channel-Assignment Problem
• Coloring a Family of Circular Arcs
• Technical Note—Optimal Scheduling of Periodic Activities
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Title not available (Why is that?)
• An Efficient Test for Circular-Arc Graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Lattice Point Covering Theorem for Rectangles
• An O(qn) algorithm to q-color a proper family of circular arcs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets
• A better performance guarantee for approximate graph coloring

Cited In (12)

• Fuzzy colouring of fuzzy graphs
• Title not available (Why is that?)
• A graph coloring approach to the deployment scheduling and unit assignment problem
• List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures
• Title not available (Why is that?)
• Scheduling policies for multi-period services
• A connection between circular colorings and periodic schedules
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• An approximation result for a periodic allocation problem
• On a graph-theoretical model for cyclic register allocation
• Pattern periodic coloring of distance graphs
• A branch-and-price algorithm for the aperiodic multi-period service scheduling problem

This page was built for publication: Periodic assignment and graph colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329789)