| 講演抄録／キーワード |
| 講演名 |
2006-01-11 14:00
Score Sequence Pair Problems of (r11,r12,r22)-Tournaments
-- Construction --
○Masaya Takahashi（Fukuoka Inst. of Tech./Waseda Univ）・Takahiro Watanabe・Takeshi Yoshimura（Waseda Univ） |
| 抄録 |
（和） |
Gを性質P(例：無向グラフ、有向グラフなど)をもつグラフとし、Sを非負で非減少な整数列とする。規定された次数列問題とは、与えられた数列Sが頂点の次数または出次数となっているようなグラフGが存在するかどうかを判定する問題である。1950年代以降、Pは広く拡張され、ErdösやHararyを代表とする多くの研究者により発展してきた。本稿ではPを以下の(1)(2)を満たす性質とする：
(1) Gは２つの重複のない頂点集合A, Bをもつ有向グラフである。
(2) Aのすべての頂点対の間には各々r11本の有向辺が存在し、Bのすべての頂点対の間には各々r22本の有向辺が存在し、AとBの頂点のすべての対の間には各々r12本の有向辺が存在する。
このときGを(r11, r12, r22)-トーナメント(“トーナメント”と略す)という。また、この問題を“トーナメント”の得点列問題(実現可能と略す)という。問題の答えがyesならばSを“トーナメント”の得点列という。近年私たちは、２つの整数列が実現可能かどうかを線形時間で判定するアルゴリズムを提案した。本稿では、実現可能な２つの整数列から“トーナメント”を構成する最適アルゴリズムを提案する。 |
| （英） |
Let G be any graph with the 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 by many researchers, such as Erdös, Harary. 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 problem is “yes.” This problem has important applications such as the communication network control problems. Recently, we proposed the algorithm for determining in linear time whether a pair of two integer sequences is realizable or not. However the following problem remains: Construct such the tournament efficiency from a score sequence pair. Solving this problem is very important for the application described above.
In this paper, we propose an optimal time algorithm for constructing such a tournament. |
| キーワード |
（和） |
アルゴリズム / グラフ理論 / 規定された次数 / 得点列 / 実現可能 / トーナメント / / |
| （英） |
algorithm / graph theory / prescribed degrees / score sequence / realizable / tournament / / |
| 文献情報 |
信学技報, vol. 105, no. 502, CAS2005-70, pp. 1-6, 2006年1月. |
| 資料番号 |
CAS2005-70 |
| 発行日 |
2006-01-04 (CAS) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
CAS |
| 開催期間 |
2006-01-11 - 2006-01-13 |
| 開催地（和） |
宮崎大学 |
| 開催地（英） |
|
| テーマ（和） |
一般 |
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
CAS |
| 会議コード |
2006-01-CAS |
| 本文の言語 |
英語 |
| タイトル（和） |
|
| サブタイトル（和） |
|
| タイトル（英） |
Score Sequence Pair Problems of (r11,r12,r22)-Tournaments |
| サブタイトル（英） |
Construction |
| キーワード(1)（和/英） |
アルゴリズム / algorithm |
| キーワード(2)（和/英） |
グラフ理論 / graph theory |
| キーワード(3)（和/英） |
規定された次数 / prescribed degrees |
| キーワード(4)（和/英） |
得点列 / score sequence |
| キーワード(5)（和/英） |
実現可能 / realizable |
| キーワード(6)（和/英） |
トーナメント / tournament |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
高橋 昌也 / Masaya Takahashi / タカハシ マサヤ |
| 第1著者 所属（和/英） |
福岡工業大学 (略称： 福岡工大)
Fukuoka Institute of Technology (略称： Fukuoka Inst. of Tech./Waseda Univ) |
| 第2著者 氏名（和/英/ヨミ） |
渡邊 孝博 / Takahiro Watanabe / ワタナベ タカヒロ |
| 第2著者 所属（和/英） |
早稲田大学 (略称： 早大)
Waseda University (略称： Waseda Univ) |
| 第3著者 氏名（和/英/ヨミ） |
吉村 猛 / Takeshi Yoshimura / ヨシムラ タケシ |
| 第3著者 所属（和/英） |
早稲田大学 (略称： 早大)
Waseda University (略称： Waseda Univ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-01-11 14:00:00 |
| 発表時間 |
25分 |
| 申込先研究会 |
CAS |
| 資料番号 |
CAS2005-70 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.502 |
| ページ範囲 |
pp.1-6 |
| ページ数 |
6 |
| 発行日 |
2006-01-04 (CAS) |
|