A new property and a faster algorithm for baseball elimination (Q2719163)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A new property and a faster algorithm for baseball elimination |
scientific article; zbMATH DE number 1608827
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new property and a faster algorithm for baseball elimination |
scientific article; zbMATH DE number 1608827 |
Statements
21 June 2001
0 references
network flow
0 references
A new property and a faster algorithm for baseball elimination (English)
0 references
The teams in a tornament are competing for first place. At each point in the season we have for each team \((i)\) a record of the number of wins \((w_i)\) so far and the number of games left to play against each team \(j\), labeled, \(g_{ij}\). With this information in hand, can one determine which teams cannot possibly win first place? Such a team is said to have been eliminated. It was shown in 1966 that a single maximum flow computation was needed to decide if a given team was eliminated. This paper describes an algorithm that will determine all eliminated teams. More importantly it does so in time proportional to a single maximum flow computation.
0 references
