@inproceedings{4e4b31dc57c5427a85ed82d0e6ff998c,
title = "Scheduling interval ordered tasks in parallel",
abstract = "We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority CRCW PRAM in O(Iog2n) time with O(n5) processors, or in O(log3 n) time with o(n4) processors. The algorithm constructs the same schedule as the one produced by the sequential algorithm (list scheduling). On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-complete.",
author = "S. Sunder and Xin He",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993 ; Conference date: 25-02-1993 Through 27-02-1993",
year = "1993",
doi = "10.1007/3-540-56503-5\_13",
language = "English",
isbn = "9783540565031",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "100--109",
editor = "Patrice Enjalbert and Alain Finkel and Wagner, \{Klaus W.\}",
booktitle = "STACS 1993 - 10th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
address = "Germany",
}