We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The computational complexity of the elimination problem in generalized sports competitions.

Kern, W. and Paulusma, Daniel (2004) 'The computational complexity of the elimination problem in generalized sports competitions.', Discrete optimization., 1 (2). pp. 205-214.


Consider a sports competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to win the competition. The computational complexity of this question depends on the way scores are allocated according to the outcome of a match. For competitions with at most 3 different outcomes of a match the complexity is already known. In practice there are many competitions in which more than 3 outcomes are possible. We determine the complexity of the above problem for competitions with an arbitrary number of different outcomes. Our model also includes competitions that are asymmetric in the sense that away playing teams possibly receive other scores than home playing teams.

Item Type:Article
Keywords:Elimination problem, NP-complete, Network flow.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:November 2004
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar