AMBIENTUM BIOETHICA BIOLOGIA CHEMIA DIGITALIA DRAMATICA EDUCATIO ARTIS GYMNAST. ENGINEERING EPHEMERIDES EUROPAEA GEOGRAPHIA GEOLOGIA HISTORIA HISTORIA ARTIUM INFORMATICA IURISPRUDENTIA MATHEMATICA MUSICA NEGOTIA OECONOMICA PHILOLOGIA PHILOSOPHIA PHYSICA POLITICA PSYCHOLOGIA-PAEDAGOGIA SOCIOLOGIA THEOLOGIA CATHOLICA THEOLOGIA CATHOLICA LATIN THEOLOGIA GR.-CATH. VARAD THEOLOGIA ORTHODOXA THEOLOGIA REF. TRANSYLVAN
|
|||||||
Rezumat articol ediţie STUDIA UNIVERSITATIS BABEŞ-BOLYAI În partea de jos este prezentat rezumatul articolului selectat. Pentru revenire la cuprinsul ediţiei din care face parte acest articol, se accesează linkul din titlu. Pentru vizualizarea tuturor articolelor din arhivă la care este autor/coautor unul din autorii de mai jos, se accesează linkul din numele autorului. |
|||||||
STUDIA INFORMATICA - Ediţia nr.Sp. Issue 1 din 2014 | |||||||
Articol: |
DEGREE SETS OF TOURNAMENTS. Autori: . |
||||||
Rezumat:
The score set of a tournament is defined as the set of its different outdegrees. In 1978 Reid [20] published the conjecture that for any set of non negative integers D there exists a tournament T whose degreeset is D. Reid proved the conjecture for tournaments containing n =1; 2 and 3 vertices. In 1986 Hager [7] published a constructive proof of the conjecture for n = 4 and 5 vertices. Yao [27] in 1989 presented an arithmetical proof of the conjecture, but general polynomial construction algorithm is not known. In [11] we described polynomial time algorithms which reconstruct the score sets containing only elements less than 7. In this paper we present and analyze earlier proposed algorithms Balancing and Shortening, further new algorithms Shifting and Hole which together reconstruct the score sets containing elements less than 9 and so give a constructive partial proof of the Reid conjecture. 2010 Mathematics Subject Classification. 68R10, 05C20.1998 CR Categories and Descriptors. G.2.2 [GRAPH THEORY]: Subtopic - Graph algorithms; F2 [ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY]:Subtopic - Computations on discrete structures. Key words and phrases. tournament, degree set, score set, analysis of algorithms.
|
|||||||