A hypocoloring model for batch scheduling

DOI10.1016/j.dam.2004.06.016zbMath1115.68118OpenAlexW2052644051MaRDI QIDQ1765371

Dominique de Werra, Vangelis Th. Paschos, Marc Demange, Jérôme Monnot

Publication date: 23 February 2005

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

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2480

zbMATH Keywords

NP-completeGraph coloringBatch schedulingchromatic schedulingApproximabilityHypocoloringsSubcoloringsWeighted colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines ⋮ Graph multi-coloring for a job scheduling application ⋮ The maximum saving partition problem ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ On split-coloring problems ⋮ Scheduling incompatible tasks on two machines

Cites Work

• More about subcolorings
• On the complexity of decomposing matrices arising in satellite communication
• Scheduling with incompatible jobs
• The thickness of graphs: A survey
• The subchromatic number of a graph
• On generalized graph colorings
• Graph Subcolorings: Complexity and Algorithms
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A hypocoloring model for batch scheduling