On the \(k\)-coloring of intervals
From MaRDI portal
Publication:1893157
DOI10.1016/0166-218X(93)E0174-WzbMath0826.68092OpenAlexW2138081211MaRDI QIDQ1893157
Errol L. Lloyd, Martin C. Carlisle
Publication date: 20 November 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0174-w
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Call control with \(k\) rejections ⋮ Heterogeneous Multi-resource Allocation with Subset Demand Requests ⋮ On packing and coloring hyperedges in a cycle ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Refined algorithms for hitting many intervals ⋮ An Exact Decomposition Approach for the Real-Time Train Dispatching Problem ⋮ Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times ⋮ Maximizing the weighted number of just‐in‐time jobs in a distributed flow‐shop scheduling system ⋮ Fixed interval scheduling with third‐party machines ⋮ Online interval scheduling on two related machines: the power of lookahead ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ The just-in-time scheduling problem in a flow-shop scheduling system ⋮ Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems ⋮ Demand Hitting and Covering of Intervals ⋮ Online interval scheduling with a bounded number of failures ⋮ Improved Randomized Results for That Interval Selection Problem ⋮ The maximum \(k\)-colorable subgraph problem and orbitopes ⋮ Bicriteria scheduling for contiguous and non contiguous parallel tasks ⋮ An experimental study of maximum profit wavelength assignment in WDM rings ⋮ AFSCN scheduling: how the problem and solution have evolved ⋮ Competitive algorithms for multistage online scheduling ⋮ Characterizing sets of jobs that admit optimal greedy-like algorithms ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ A unified model and algorithms for temporal map labeling ⋮ Interval scheduling on related machines ⋮ Path problems in generalized stars, complete graphs, and brick wall graphs ⋮ Just-in-time scheduling with controllable processing times on parallel machines ⋮ Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs ⋮ 1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings ⋮ Improved randomized results for the interval selection problem ⋮ Wavelength assignment in multifiber star networks ⋮ A simple and effective hybrid genetic search for the job sequencing and tool switching problem ⋮ Some approximation algorithms for the clique partition problem in weighted interval graphs ⋮ Multistage interval scheduling games ⋮ Online interval scheduling to maximize total satisfaction ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Models and algorithms for energy-efficient scheduling with immediate start of jobs ⋮ Interval scheduling with economies of scale ⋮ Maximizing profits of routing in WDM networks ⋮ Online scheduling of jobs with fixed start times on related machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for a special case of disjoint set union
- Scheduling jobs with fixed start and end times
- The maximum k-colorable subgraph problem for chordal graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Efficiency of a Good But Not Linear Set Union Algorithm
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems