A Recursive Algorithm to Generate Balanced Weekend Tournaments

Authors

  • Richard Hoshino Quest University Canada

Keywords:

sports scheduling, tournament scheduling, hamiltonian cycles, hamiltonian decompositions

Abstract

In this paper, we construct a Balanced Weekend Tournament, motivated by the real-life problem of scheduling an n-team double round-robin season schedule for a Canadian university soccer league. In this 6-team league, games are only played on Saturdays and Sundays, with the condition that no team has two road games on any weekend. The implemented regular-season schedule for n = 6 was best-possible, but failed to meet an important "compactness" criterion, as the 10-game tournament required more than five weekends to complete. The motivation for this paper was to determine whether an optimal season schedule, satisfying all of the league's constraints on compact balanced play, could be constructed for sports leagues with n > 6 teams. We present a simple recursive algorithm to answer this question for all even n > 6. As a corollary, our construction gives us an explicit solution to a challenging and well-known graph theory question, namely the problem of decomposing the complete directed graph K*2m into 2m–1 directed Hamiltonian cycles of length 2m.

Downloads

Published

2018-04-26

How to Cite

Hoshino, R. (2018). A Recursive Algorithm to Generate Balanced Weekend Tournaments. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12076