Paper Info

Title | ||
---|---|---|

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

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)$. |

Year | DOI | Venue |
---|---|---|

2001 | 10.1016/S0020-0190(01)00142-9 | Inf. Process. Lett. |

Keywords | Field | DocType |

rightarrow w,constructive proof,rightarrow v,rightarrow u,efficient algorithm,tournament,sorting algorithm,computational complexity | Discrete mathematics,Tournament,Constructive proof,Combinatorics,Sorting,Sorting algorithm,Mathematics | Journal |

Volume | Issue | ISSN |

79 | 6 | 0020-0190 |

Citations | PageRank | References |

3 | 0.71 | 0 |

Authors | ||

2 |