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(n3) processors and takes O(log 2n) 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.

Authors

• Hermann Jung
• Maria Serna
• Paul Spirakis

Keywords

• Scheduling
• Parallel algorithms
• PRAM