An efficient deterministic parallel algorithm for two processors precedence constraint scheduling

AbstractWe present here a new deterministic parallel algorithm for the two-processor scheduling problem. The algorithm uses only O(n3) processors and takes O(log2n) 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