An Optimal Algorithm to Find Champions of Tournament Graphs

摘要

A tournament graph T = (V, E) is an oriented complete graph, which can be used to model a round-robin tournament between n players. In this short paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. Our goal is to solve the problem by minimizing the number of arc lookups, i.e., the number of matches played. We prove that finding a champion requires Ω(ln) comparisons, where l is the number of matches lost by the champion, and we present a deterministic algorithm matching this lower bound without knowing (.. Solving this problem has important implications on several Information Retrieval applications including Web search, conversational Al, machine translation, question answering, recommender systems, etc.