The mutual exclusion scheduling problem for permutation and comparability graphs.

DOI10.1016/S0890-5401(02)00028-7MaRDI QIDQ1401918zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Mutual exclusion scheduling with interval graphs or related classes. I
• Mutual exclusion scheduling with interval graphs or related classes. II
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• Comparability graph augmentation for some multiprocessor scheduling problems

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A graph coloring algorithm for large scale scheduling problems
• A note on the decomposition of graphs into isomorphic matchings
• An existential problem of a weight-controlled subset and its application to school timetable construction
• Bounded vertex colorings of graphs
• Chromatic optimisation: Limitations, objectives, uses, references
• scientific article; zbMATH DE number 3903967 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 4057269 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 512913 (Why is no real title available?)
• scientific article; zbMATH DE number 736352 (Why is no real title available?)
• scientific article; zbMATH DE number 1128827 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• scientific article; zbMATH DE number 871903 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• Mutual exclusion scheduling
• NP-completeness of graph decomposition problems
• Optimal Sequencing of Two Equivalent Processors
• Partial orders of dimension 2
• The complexity of generalized clique packing
• The χt-coloring problem
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(28)

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

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

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