The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

  
       
         
    STUDIA INFORMATICA - Issue no. Sp. Issue 1 / 2014  
         
  Article:   DEGREE SETS OF TOURNAMENTS.

Authors:  . 		 
       
         
  Abstract:   The score set of a tournament is de fined as the set of its diff erent 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 Classifi cation. 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.
 
         
     
         
         
      Back to previous page