The mutual exclusion scheduling problem for permutation and comparability graphs.

DOI10.1016/S0890-5401(02)00028-7zbMath1054.68019OpenAlexW2053227662MaRDI QIDQ1401918

Klaus Jansen

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(02)00028-7

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (24)

Loading, unloading and premarshalling of stacks in storage areas: survey and classification ⋮ The bounded beam search algorithm for the block relocation problem ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ An asymptotically optimal algorithm for online stacking ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Partitioning a weighted partial order ⋮ Track assignment ⋮ Batch processing with interval graph compatibilities between tasks ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Efficient algorithms for the double traveling salesman problem with multiple stacks ⋮ A branch-and-cut algorithm for the restricted block relocation problem ⋮ Solution approaches for storage loading problems with stacking constraints ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Generalised online colouring problems in overlap graphs ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ The parallel stack loading problem minimizing the number of reshuffles in the retrieval stage ⋮ Clique partitioning with value-monotone submodular cost ⋮ Equitable colorings of bounded treewidth graphs

Cites Work

• Bounded vertex colorings of graphs
• A note on the decomposition of graphs into isomorphic matchings
• The complexity of generalized clique packing
• A graph coloring algorithm for large scale scheduling problems
• An existential problem of a weight-controlled subset and its application to school timetable construction
• Chromatic optimisation: Limitations, objectives, uses, references
• NP-completeness of graph decomposition problems
• Mutual exclusion scheduling
• The χt-coloring problem
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Optimal Sequencing of Two Equivalent Processors
• Partial orders of dimension 2
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The mutual exclusion scheduling problem for permutation and comparability graphs.