Journal article
Searching for Sorted Sequences of Kings in Tournaments
SIAM journal on computing, v 32(5), pp 1201-1209
01 Jan 2003
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A tournamentTn is an orientation of a complete graph on n vertices. A king in a tournament is a vertex from which every other vertex is reachable by a path of length at most 2. A sorted sequence of kings in a tournament Tn is an ordered list of its vertices u1, u2, . . ., un such that ui dominates $u_{i+1}$ ($u_i \rightarrow u_{i+1}$) and $u_i$ is a king in the subtournament induced by $\{u_j: i \le j \le n\}$ for each i=1,2, . . .,n-1. In particular, if Tn is transitive, searching for a sorted sequence of kings in Tn is equivalent to sorting a set of n numbers. In this paper, we try to find a sorted sequence of kings in a general tournament by asking the following type of binary question: "What is the orientation of the edge between two specified vertices u, v?" The cost for finding a sorted sequence of kings is the minimum number of binary questions asked in order to guarantee the finding of a sorted sequence of kings. Using an adversary argument proposed in this paper, we showthat the cost for finding a sorted sequence of kings in Tn is $\Theta(n^{3/2})$ in the worst case, thus settling the order of magnitude of this question. We also show that the cost for finding a king in Tn is $\Omega(n^{4/3})$ and O(n3/2) in the worst case. Finally, we show a connection between a sorted sequence of kings and a median order in a tournament.
Metrics
Details
- Title
- Searching for Sorted Sequences of Kings in Tournaments
- Creators
- Jian ShenLi ShengJie Wu
- Publication Details
- SIAM journal on computing, v 32(5), pp 1201-1209
- Publisher
- Society for Industrial and Applied Mathematics
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000185629400006
- Scopus ID
- 2-s2.0-0344584886
- Other Identifier
- 991019168875704721
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, Theory & Methods
- Mathematics, Applied