For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Score Sequence Problems of r-Tournaments
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/02/25
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)>>
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.