Score Sequence Problems of <I>r</I>-Tournaments

Masaya TAKAHASHI

Score Sequence Problems of r-Tournaments

Masaya TAKAHASHI

Full Text Views

0

Cite this

Summary :

A sequence of nonnegative integers s=(S₁, s₂, , s_n) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v₁, v₂, , v_n such that deg₊(v_j)=s_j and deg_-(v_j)=r(n-1) -s_j 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.2 pp.377-385

Publication Date: 1997/02/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Graphs and Networks

Cite this

Copy

Masaya TAKAHASHI, "Score Sequence Problems of r-Tournaments" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 2, pp. 377-385, February 1997, doi: .
Abstract: A sequence of nonnegative integers s=(S₁, s₂, , s_n) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v₁, v₂, , v_n such that deg₊(v_j)=s_j and deg_-(v_j)=r(n-1) -s_j 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_2_377/_p

Copy

@ARTICLE{e80-a_2_377,
author={Masaya TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Score Sequence Problems of r-Tournaments},
year={1997},
volume={E80-A},
number={2},
pages={377-385},
abstract={A sequence of nonnegative integers s=(S₁, s₂, , s_n) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v₁, v₂, , v_n such that deg₊(v_j)=s_j and deg_-(v_j)=r(n-1) -s_j 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.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Score Sequence Problems of r-Tournaments
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 377
EP - 385
AU - Masaya TAKAHASHI
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 1997
AB - A sequence of nonnegative integers s=(S₁, s₂, , s_n) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v₁, v₂, , v_n such that deg₊(v_j)=s_j and deg_-(v_j)=r(n-1) -s_j 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.
ER -