Score Sequence Problems of r-Tournaments


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.2   pp.377-385
Publication Date: 1997/02/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
r-tournament,  r-bitournament,  k-edge-connected,  score sequence,  

Full Text: PDF(770.9KB)>>
Buy this Article

A sequence of nonnegative integers s=(S1, s2, , sn) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v1, v2, , vn such that deg+(vj)=sj and deg-(vj)=r(n-1) -sj for each j=1, 2, , n. The score sequence problem of an r-tournament is: Given some positive integer r and a sequence of nonnegative integers, determine whether it is a score sequence of an r-tournament or not. In this paper, we consider several variations of the score sequence problem of an r-tournament, and give efficient algorithms.