2007年2月
Score sequence pair problems of (r(11), r(12), r(22))-tournaments - Determination of realizability
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- ,
- ,
- 巻
- E90D
- 号
- 2
- 開始ページ
- 440
- 終了ページ
- 448
- 記述言語
- 英語
- 掲載種別
- DOI
- 10.1093/ietisy/e90-d.2.440
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
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 r(11) (r(22), respectively) directed edges between every pair of vertices in A(B), and r(12) directed edges between every pair of vertex in A and vertex in B.
Then G is called an (r(11), r(12), r(22))-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.
(1) G is a directed graph with two disjoint vertex sets A and B.
(2) There are r(11) (r(22), respectively) directed edges between every pair of vertices in A(B), and r(12) directed edges between every pair of vertex in A and vertex in B.
Then G is called an (r(11), r(12), r(22))-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.
- リンク情報
- ID情報
-
- DOI : 10.1093/ietisy/e90-d.2.440
- ISSN : 0916-8532
- Web of Science ID : WOS:000244546400008