Mutual exclusion scheduling with interval graphs or related classes. II

DOI10.1016/J.DAM.2007.08.017MaRDI QIDQ2476265zbMATH OpenOpenAlexFDO

Authors Frédéric Gardi

Publication date 18 March 2008

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.08.017

zbMATH Keywords

bounded coloringchromatic schedulinggraph algorithmsinterval graphsworkforce planning

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Mutual exclusion scheduling with interval graphs or related classes. I
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Mutual exclusion scheduling
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs

Cites work

• A note on the decomposition of graphs into isomorphic matchings
• An introduction to timetabling
• Betweenness, orders and interval graphs
• Bounded vertex coloring of trees
• Bounded vertex colorings of graphs
• Claw-free graphs---a survey
• Extensions of coloring models for scheduling purposes
• Graph Classes: A Survey
• How To Color Claw-Free Perfect Graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• Kernels in perfect line-graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Line perfect graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Mathematical Foundations of Computer Science 2004
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• NP-completeness of graph decomposition problems
• On line perfect graphs
• Restricted coloring models for timetabling
• Restrictions of graph partition problems. I
• Some uses of hypergraphs in timetabling
• The ellipsoid method and its consequences in combinatorial optimization
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• The NP-Completeness of Edge-Coloring

Cited in

(6)

• Mutual exclusion scheduling with interval graphs or related classes. I
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Scheduling identical jobs on uniform machines with a conflict graph
• Bounded max-colorings of graphs
• On partitioning interval graphs into proper interval subgraphs and related problems
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms

This page was built for publication: Mutual exclusion scheduling with interval graphs or related classes. II

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