William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
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.
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
Minghong Fang, Zifan Zhang, et al.
CCS 2024