Complexity of the traveling tournament problem

Clemens Thielen, Stephan Westphal

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

We consider the complexity of the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The problem was supposed to be computationally hard ever since its proposal in 2001. Recently, the first NP-completeness proof has been given for the variant of the problem were no constraints on the number of consecutive home games or away games of a team are considered. The complexity of the original traveling tournament problem including these constraints, however, is still open. In this paper, we show that this variant of the problem is strongly NP-complete when the upper bound on the maximal number of consecutive away games is set to 3.

Original languageEnglish
Pages (from-to)345-351
Number of pages7
JournalTheoretical Computer Science
Volume412
Issue number4-5
DOIs
StatePublished - 4 Feb 2011
Externally publishedYes

Keywords

  • Computational complexity
  • Scheduling
  • Timetabling
  • Traveling tournament problem

Fingerprint

Dive into the research topics of 'Complexity of the traveling tournament problem'. Together they form a unique fingerprint.

Cite this