Periodic assignment and graph colouring
From MaRDI portal
Publication:1329789
DOI10.1016/0166-218X(92)00036-LzbMath0807.05030MaRDI QIDQ1329789
Jan Karel Lenstra, Emile H. L. Aarts, Jaap Wessels, Jan H. M. Korst
Publication date: 31 July 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
coloringinterval graphsNP-hard problemcircular-arc graphsperiodic assignmentperiodic-interval graphs
Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15) Applications of graph theory to circuits and networks (94C15)
Related Items
Scheduling policies for multi-period services, Fixed interval scheduling: models, applications, computational complexity and algorithms, A branch-and-price algorithm for the aperiodic multi-period service scheduling problem, Unnamed Item, On a graph-theoretical model for cyclic register allocation, Fuzzy colouring of fuzzy graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A better performance guarantee for approximate graph coloring
- An O(qn) algorithm to q-color a proper family of circular arcs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- Incidence matrices and interval graphs
- Representation of a finite graph by a set of intervals on the real line
- Technical Note—Optimal Scheduling of Periodic Activities
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- An Optimal Solution for the Channel-Assignment Problem
- An Efficient Test for Circular-Arc Graphs
- Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- 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
- Coloring a Family of Circular Arcs
- On the complexity of computing the measure of ∪[a i ,b i ]
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- The Lattice Point Covering Theorem for Rectangles
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
