tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not." />
 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 Pair Problems of (r11, r12, r22)-Tournaments--Determination of Realizability--Masaya TAKAHASHI  Takahiro WATANABE  Takeshi YOSHIMURA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E90-D   No.2   pp.440-448Publication Date: 2007/02/01 Online ISSN: 1745-1361 DOI: 10.1093/ietisy/e90-d.2.440 Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)Category: Graph AlgorithmsKeyword: algorithm,  graph theory,  prescribed degrees,  score sequence,  tournament,  Full Text: PDF(446.7KB)>> Buy this Article Summary:  Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):(1) G is a directed graph with two disjoint vertex sets A and B. (2) There are r11 (r22, respectively) directed edges between every pair of vertices in A(B), and r12 directed edges between every pair of vertex in A and vertex in B. Then G is called an (r11, r12, r22)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.