Mutual exclusion scheduling with interval graphs or related classes. I

DOI10.1016/j.dam.2008.04.016zbMath1155.90381OpenAlexW2043493954MaRDI QIDQ1003752

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 algorithmsbounded coloringinterval graphsworkforce planningchromatic scheduling

Mathematics Subject Classification ID

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

Related Items

Scheduling: agreement graph vs resource constraints, On partitioning interval graphs into proper interval subgraphs and related problems, An exact algorithm for parallel machine scheduling with conflicts, New results in two identical machines scheduling with agreement graphs, Scheduling with machine conflicts, Scheduling on uniform machines with a conflict graph: complexity and resolution, Flow shop scheduling problem with conflict graphs, Unnamed Item, Scheduling jobs on identical machines with agreement graph, On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups, Scheduling identical jobs on uniform machines with a conflict graph, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Two-machine open shop problem with agreement graph, Clique partitioning with value-monotone submodular cost, Open shop scheduling problems with conflict graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Simple linear time recognition of unit interval graphs
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• Interval graphs and interval orders
• Chromatic optimisation: Limitations, objectives, uses, references
• NP-completeness of graph decomposition problems
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Restricted coloring models for timetabling
• Mutual exclusion scheduling
• Matching and multidimensional matching in chordal and strongly chordal graphs
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Parallel algorithms for maximum matching in complements of interval graphs and related problems
• Scheduling with constrained processor allocation for interval orders
• Efficient algorithms for interval graphs and circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• Graph Classes: A Survey
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Reducibility among Combinatorial Problems
• Mathematical Foundations of Computer Science 2004
• Maximum matching in a convex bipartite graph
• Bounded vertex coloring of trees
• Maximum skew-symmetric flows