Fernando Martinez, Juntao Chen, et al.
AAAI 2025
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.
Fernando Martinez, Juntao Chen, et al.
AAAI 2025
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Imran Nasim, Melanie Weber
SCML 2024
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008