Mutual exclusion scheduling with interval graphs or related classes. I

DOI10.1016/J.DAM.2008.04.016MaRDI QIDQ1003752zbMATH OpenOpenAlexFDO

Authors Frédéric Gardi

Publication date 4 March 2009

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

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

zbMATH Keywords

graph algorithmsinterval graphsworkforce planningchromatic schedulingbounded coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Mutual exclusion scheduling with interval graphs or related classes. II
• 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

Cites work

• scientific article; zbMATH DE number 1640601 (Why is no real title available?)
• 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 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• scientific article; zbMATH DE number 2090048 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Bounded vertex coloring of trees
• Chromatic optimisation: Limitations, objectives, uses, references
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
• Graph Classes: A Survey
• Interval graphs and interval orders
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Mathematical Foundations of Computer Science 2004
• Maximum matching in a convex bipartite graph
• Maximum skew-symmetric flows
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• NP-completeness of graph decomposition problems
• Parallel algorithms for maximum matching in complements of interval graphs and related problems
• Reducibility among combinatorial problems
• Restricted coloring models for timetabling
• Restrictions of graph partition problems. I
• Scheduling with constrained processor allocation for interval orders
• Simple linear time recognition of unit interval graphs
• Some uses of hypergraphs in timetabling
• The Complexity of Coloring Circular Arcs and Chords
• The mutual exclusion scheduling problem for permutation and comparability graphs.

Cited in

(21)

• Periodic assignment and graph colouring
• Kempe equivalence of almost bipartite graphs
• Scheduling jobs on identical machines with agreement graph
• Mutual exclusion scheduling with interval graphs or related classes. II
• New results in two identical machines scheduling with agreement graphs
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• On partitioning interval graphs into proper interval subgraphs and related problems
• Scheduling identical jobs on uniform machines with a conflict graph
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Clique partitioning with value-monotone submodular cost
• An exact algorithm for parallel machine scheduling with conflicts
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• scientific article; zbMATH DE number 2090048 (Why is no real title available?)
• Scheduling with machine conflicts
• Strip Graphs: Recognition and Scheduling
• On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups
• Scheduling: agreement graph vs resource constraints
• Flow shop scheduling problem with conflict graphs
• Scheduling on uniform machines with a conflict graph: complexity and resolution
• Two-machine open shop problem with agreement graph
• Open shop scheduling problems with conflict graphs

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

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