John S. Lew
Mathematical Biosciences
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.
John S. Lew
Mathematical Biosciences
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence