DIMACS TR: 2000-12
An Efficient Sorting Algorithm for a Sequence of Kings in a Tournament
Authors: Jie Wu and Li Sheng
ABSTRACT
A king $u$ in a tournament is a player who beats ($\rightarrow$)
any other player $v$ {\em directly or indirectly}.
That is, either $u \rightarrow v$ or there exists a third
player $w$ such that $u \rightarrow w$ and $w \rightarrow v$.
A sorting sequence of kings in a tournament of $n$ players
is a sequence of players, $S=(u_1$, $u_2$, ..., $u_n)$, such that $u_i
\rightarrow u_{i+1}$ and $u_i$ in a king in the
sub-tournament $T_{u_i}$ induced by $u_i, u_{i+1},
..., u_n$ for $i=1, 2,..., n-1$. The existence
of a sorting sequence of kings in any tournament
is shown \cite{LouW00} where a sorting algorithm with a
complexity of $\Theta(n^{3})$ is given.
In this paper, we present a constructive proof for the existence of
a sorting sequence of kings of
a tournament and propose an efficient algorithm
with a complexity of $\Theta(n^2)$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-12.ps.gz
DIMACS Home Page