Document - An Optimal Algorithm to Find Champions of Tournament Graphs

2019

Conference article Open Access

An Optimal Algorithm to Find Champions of Tournament Graphs

Beretta L., Nardini F. M., Trani R., Venturini R.

round-robin tournament tournament graph copeland winner

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 l . Solving this problem has important implications on several Information Retrieval applications including Web search, conversational AI, machine translation, question answering, recommender systems, etc.

Source: SPIRE 2019: International Symposium on String Processing and Information Retrieval, pp. 267–273, Segovia, Spagna, 07/10/2019, 09/10/2019

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:415716,
	title = {An Optimal Algorithm to Find Champions of Tournament Graphs},
	author = {Beretta L. and Nardini F. M. and Trani R. and Venturini R.},
	doi = {10.1007/978-3-030-32686-9_19},
	booktitle = {SPIRE 2019: International Symposium on String Processing and Information Retrieval, pp. 267–273, Segovia, Spagna, 07/10/2019, 09/10/2019},
	year = {2019}
}