An efficient sorting algorithm for a sequence of kings in a tournament

A king u in a tournament is a player who beats any other player v directly or indirectly. That is, either u --> v (u beats v) or there exists a third player w such that u -->. w and w --> v. A sorted sequence of kings in a to urnament of n players is a sequence of players, S = (u(1), u(2), - - -, u(n )), such that u(i) --> u(i+1) and u(i) in a king in sub-tournament T-ui = { u(i), u(i+1),..., u(n)} for i = 1, 2,..., n - 1. The existence of a sorted sequence of kings in any tournament is shown by Lou et al. [Proc. 31st Sout heastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, 200 0] where a sorting algorithm with a complexity of Theta (n(3)) is given. In this paper, we present another constructive proof for the existence of a s orted sequence of kings of a tournament and propose an efficient algorithm with a complexity of Theta (n(2)). (C) 2001 Elsevier Science B.V. All right s reserved.