Optimal parallel construction of prescribed tournaments

Abstract

A tournament is a digraph in which every pair of vertices is connected by exactly one arc. The score list of a tournament is the sorted list of the out-degrees of its vertices. Given a nondecreasing sequence of nonnegative integers, is it the score list of some tournament? There is a simple test for answering this question. There is also a simple sequential algorithm for constructing a tournament with a given score list. However, this algorithm has a greedy nature, and seems hard to parallelize. We present a simple parallel algorithm for the construction problem. Our algorithm runs in time O(log n) and uses O(n2/log n) processors on a CREW PRAM, where n is the number of vertices. Since the size of the output is Θ(n2), our algorithm achieves optimal speedup. The tournament constructed has the property that it is the closest possible to a transitive tournament in a precise sense. © 1990.