Comparability graph augmentation for some multiprocessor scheduling problems

DOI10.1016/S0166-218X(96)00037-6MaRDI QIDQ5961606zbMATH OpenOpenAlexFDO

Authors Paolo Dell'Olmo, Maria Grazia Speranza, Zsolt Tuza

Publication date 21 April 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

perfect graphscomparability graph

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)

Recommendations

• scientific article; zbMATH DE number 4049080
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Time slot scheduling of compatible jobs
• Publication:3477945
• scientific article; zbMATH DE number 3908482

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Efficiency and effectiveness of normal schedules on three dedicated processors
• Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths
• Nonpreemptive scheduling of independent tasks with prespecified processor allocations
• Scheduling multiprocessor tasks on three dedicated processors
• The complexity of scheduling independent two-processor tasks on dedicated processors

Cited in

(4)

• Orienting graphs to optimize reachability
• An approximation result for the interval coloring problem on claw-free chordal graphs
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• An approximation result for a periodic allocation problem

This page was built for publication: Comparability graph augmentation for some multiprocessor scheduling problems

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