<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The score set of a tournament is defined as the set of its different outdegrees. In 1978 Reid [15] published the conjecture that for any set of nonnegative integers D there exists a tournament T whose degree set is D. Reid proved the conjecture for tournaments containing n = 1, 2, and 3 vertices. In 1986 Hager [4] published a constructive proof of the conjecture for n = 4 and 5 vertices. In 1989 Yao [18] presented an arithmetical proof of the conjecture, but general polynomial construction algorithm is not known. In [6] we described polynomial time algorithms which reconstruct the score sets containing only elements less than 7. In [5] we improved this bound to 9. </p><p>In this paper we present and analyze new algorithms Hole-Map, Hole-Pairs, Hole-Max, Hole-Shift, Fill-All, Prefix-Deletion, and using them improve the above bound to 12, giving a constructive partial proof of Reid’s conjecture.</p></abstract>

The score set of a tournament is defined as the set of its different outdegrees. In 1978 Reid [15] published the conjecture that for any set of nonnegative integers D there exists a tournament T whose degree set is D. Reid proved the conjecture for tournaments containing n = 1, 2, and 3 vertices. In 1986 Hager [4] published a constructive proof of the conjecture for n = 4 and 5 vertices. In 1989 Yao [18] presented an arithmetical proof of the conjecture, but general polynomial construction algorithm is not known. In [6] we described polynomial time algorithms which reconstruct the score sets containing only elements less than 7. In [5] we improved this bound to 9. In this paper we present and analyze new algorithms Hole-Map, Hole-Pairs, Hole-Max, Hole-Shift, Fill-All, Prefix-Deletion, and using them improve the above bound to 12, giving a constructive partial proof of Reid’s conjecture.

Reconstruction of score sets

Eötvs Loránd University, Faculty of Informatics, 1117 Budapest, Pázmány Péter sétány 1/C., Hungary

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Reconstruction of score sets"}

The score set of a tournament is defined as the set of its different outdegrees. In 1978 Reid [15] published the conjecture that for any set of nonnegative...

Reconstruction of score sets

Publié en ligne: 27 janv. 2015

Pages: 210 - 229

Reçu: 28 juin 2014

DOI: https://doi.org/10.1515/ausi-2015-0005

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.