Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Journal article
An efficient sorting algorithm for a sequence of kings in a tournament
Information processing letters, v 79(6)
2001
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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 tournament 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
u
i
={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 Southeastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, 2000] where a sorting algorithm with a complexity of
Θ(n
3)
is given. In this paper, we present another constructive proof for the existence of a sorted sequence of kings of a tournament and propose an efficient algorithm with a complexity of
Θ(n
2)
.
Metrics
Details
- Title
- An efficient sorting algorithm for a sequence of kings in a tournament
- Creators
- Jie Wu - Florida Atlantic UniversityLi Sheng - Drexel University
- Publication Details
- Information processing letters, v 79(6)
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000170855100008
- Scopus ID
- 2-s2.0-0035975707
- Other Identifier
- 991019169009304721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Information Systems