An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
We present here a new deterministic parallel algorithm for the two-processor scheduling problem. The algorithm uses only O(n(3)) processors and takes O(log(2)n) time on a CREW PRAM. In order to prove the above bounds we show how to compute in NC the lexicographically first matching for a special kind of convex bipartite graphs. (C) 2002 Elsevier Science B.V. All rights reserved.
parallel algorithms scheduling pram