The Taming of Two Alley CATs
Daniel Recoskie, Joe Sawada · 2012
Round robin tournaments are used in a wide variety of competition settings and especially in recreational sports leagues. The outcomes of such tournaments can be modelled by an orientation of the edges of a complete graph, where each vertex corresponds to a unique competitor. A score sequence is an nondecreasing sequence of the out-degrees of such a graph. In this paper we analyze two previously known algorithms that exhaustively generate all feasible score sequences for a given number of competitors n. In both cases, we prove that the algorithms run in Constant Amortized Time: they are CAT.