Name
Abstract | ||
|---|---|---|
A tournament Tn 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 show that 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1137/S0097539702410053 | SIAM Journal on Computing |
Keywords | Field | DocType |
tournament,n vertex,n number,binary question,specified vertices u,divide-and-conquer algorithm,rightarrow u,vertices u1,Sorted Sequences,king,general tournament,median order,sorted sequence of kings,recursive relation,tournament Tn,worst case,adversary argument | Discrete mathematics,Complete graph,Combinatorics,Tournament,Vertex (geometry),Directed graph,Omega,Mathematics,Binary number,Transitive relation | Journal |
Volume | Issue | ISSN |
32 | 5 | 0097-5397 |
Citations | PageRank | References |
2 | 0.49 | 4 |
Authors | ||
3 | ||