@inproceedings{ac8f8abbfdae42749d571bfa0594ce70,
title = "Efficient parallel algorithms for scheduling with tree precedence constraints",
abstract = "We are interested in the parallel complexity of computing a minimum length schedule for executing n tasks of equal length on m identical processors constrained by a tree precedence relation. While this problem can be solved in linear time sequentially, the best known parallel algorithms require O(log n) time using n2 processors or O(log2 n) time on n processors. In this paper we present two new parallel algorithms. The first runs in time O(m log n) using n/log n processors of an EREW PRAM and hence is work and time optimal for any constant m. The other runs in time O(log n log m) using n/log m EREW PRAM processors.",
author = "Mayr, \{Ernst W.\} and Hans Stadtherr",
note = "Publisher Copyright: {\textcopyright} 1996, Springer Verlag. All rights reserved.; 2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996 ; Conference date: 26-08-1996 Through 29-08-1996",
year = "1996",
doi = "10.1007/bfb0024747",
language = "English",
isbn = "3540616276",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "543--554",
editor = "Luc Bouge and Pierre Fraigniaud and Anne Mignotte and Yves Robert",
booktitle = "Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings",
}