×

zbMATH — the first resource for mathematics

Deciding football sequences. (English) Zbl 1305.05088
Summary: An open problem posed by the first author is the complexity to decide whether a sequence of nonnegative integer numbers can be the final score of a football tournament. In this paper we propose polynomial time approximate and exponential time exact algorithms which solve the problem.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite