The complexity of short schedules for uet bipartite graphs
RAIRO - Operations Research (2010)
- Volume: 33, Issue: 3, page 367-370
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topBampis, Evripidis. "The complexity of short schedules for uet bipartite graphs ." RAIRO - Operations Research 33.3 (2010): 367-370. <http://eudml.org/doc/197782>.
@article{Bampis2010,
abstract = {
We show that the problem of deciding if there is a schedule
of length three for the multiprocessor scheduling problem on identical
machines and unit execution time tasks in -complete even for bipartite
graphs, i.e. for precedence graphs of depth one. This complexity result
extends a classical result of Lenstra and Rinnoy Kan [5].
},
author = {Bampis, Evripidis},
journal = {RAIRO - Operations Research},
keywords = {Schedule; multiprocessor; bipartite graph; complexity. ; schedule; complexity; multiprocessor scheduling problem},
language = {eng},
month = {3},
number = {3},
pages = {367-370},
publisher = {EDP Sciences},
title = {The complexity of short schedules for uet bipartite graphs },
url = {http://eudml.org/doc/197782},
volume = {33},
year = {2010},
}
TY - JOUR
AU - Bampis, Evripidis
TI - The complexity of short schedules for uet bipartite graphs
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 3
SP - 367
EP - 370
AB -
We show that the problem of deciding if there is a schedule
of length three for the multiprocessor scheduling problem on identical
machines and unit execution time tasks in -complete even for bipartite
graphs, i.e. for precedence graphs of depth one. This complexity result
extends a classical result of Lenstra and Rinnoy Kan [5].
LA - eng
KW - Schedule; multiprocessor; bipartite graph; complexity. ; schedule; complexity; multiprocessor scheduling problem
UR - http://eudml.org/doc/197782
ER -
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.