On the \(k\)-coloring of intervals

DOI10.1016/0166-218X(93)E0174-WzbMath0826.68092OpenAlexW2138081211MaRDI QIDQ1893157

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

zbMATH Keywords

\(k\)-coloring

Mathematics Subject Classification ID

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