权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

ネットワーク上の通信スケジューリングの分散アルゴリズム

网络上通信调度的分布式算法

基本信息

批准号：
09780230
负责人：
周暁
金额：
$ 1.22万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

平成10年で度は通信スケジューリングをグラフを利用してモデル化し,通信を効率よく実行するスケジューリングを与えるアルゴリズムの研究開発を行なった.グラフの彩色問題とスケジュール問題には密接な関連がある.いくつかの彩色アルゴリズムはスケジューリングアルゴリズムに応用されている.最近では高級言語のコンパイルのレジスタ変数の自動スケジュールなどに応用された.辺彩色問題はNP-完全であり,一般のグラフに対してこの問題を解く効率のよいアルゴリズムは存在しないと予想されている.我々はグラフのクラスを限定したとき,効率の良いアルゴリズムを考えた.即ち,部分κ-木に対して全彩色問題を解く多項式時間アルゴリズムを開発した.グラフGの全彩色とはGの全ての点と辺をどの隣接する2点,どの隣接する2辺,どの1点とそれに接続する辺も全て異なる色になるように最小色数で彩色することである.与えられた部分κ-木の,最小色数を用いた全彩色を求める多項式時間アルゴリズムは今まで知られていなかった.私たちはそのような最初のアルゴリズムを与えた.この成果を国際会議WG'98(Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science)で発表した.辺ランク付け問題もスケジューリング問題によく応用されることが知られている.私たちは与えられた木を,最小のランク数でc-辺ランク付けする多項式時間のアルゴリズムを与える.この結果がIEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciencesに掲載された.また,もっと広いグラフのクラス,部分κ木に対しても我々は最小のランク数でc-辺ランク付けする多項式時間のアルゴリズムを与えた.この成果を国際会議ICCIT'98(Procedings of International Conference on Computer and Information Technology)で発表した.

In the 10th year of Heisei, the research and development of communication efficiency was carried out. The color problem is closely related to each other. In the middle of the day, the color of the house is changed. Recently, high-level speech is used in the automatic transmission of information. The color problem is NP-complete, and the problem is solved in general. I want to make sure that you have the right answer. That is to say, partial κ-wood solution to full color problem is developed in polynomial time. The full color of G has two points, two adjacent points, one adjacent point, two adjacent points, two adjacent points, one adjacent point, two adjacent points, two adjacent points, two The minimum number of colors is calculated using the full color polynomial. It's the first time I've ever seen a girl. WG'98(Proceedings of the 24th International Workshop on Graph-Theoretical Concepts in Computer Science) was held. The problem is that the problem is not solved. The problem is solved. The minimum number of polynomials is the number of polynomials. The results are published in IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences. In this case, the minimum number of classes is the number of classes, and the polynomial time is the number of classes. ICCIT'98(Proceedings of International Conference on Computer and Information Technology)