2018/01/15 by Gregory Gutin, George B. Mertzios, Gutin, Gregory +3
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1801.04702
arxiv created 2018/01/15 · openalex publication_date 2018/01/15 · arxiv updated 2018/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex x in a tournament T is called a king if for every vertex y of T there is a directed path from x to y of length at most 2. It is not hard to show that every vertex of maximum out-degree in a tournament is a king. However, tournaments may have kings which are not vertices of maximum out-degree. A binary inquiry asks for the orientation of the edge between a pair of vertices and receives the answer. The cost of finding a king in an unknown tournament is the number of binary inquiries required to detect a king. For the cost of finding a king in a tournament, in the worst case, Shen, Sheng and Wu (SIAM J. Comput., 2003) proved a lower and upper bounds of Ω(n4/3) and O(n3/2), respectively. In contrast to their result, we prove that the cost of finding a vertex of maximum out-degree is n \choose 2 -O(n) in the worst case.