通信スケジューリングのグラフアルゴリズムによる解法

使用图算法的通信调度解决方案

• 批准号: 13780187
• 负责人: 周 暁
• 金额: $ 0.51万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780187/
• 关键词: グラフ; アルゴリズム; リスト辺彩色; 多重彩色; 部分k木; 直並列グラフ; 彩色; 重み付き彩色; 木

今年度は効率のよい通信スケジューリングのアルゴリズムをグラフアルゴリズム、特にリスト辺彩色や多重彩色アルゴリズムを応用して研究開発を行なった。リスト辺彩色や多重彩色問題は辺彩色や点彩色問題の一般化であり、NP-困難である。一般のグラフに対してはこの問題を解く効率の良いアルゴリズムが存在しないと予想されている。我々はグラフのクラスを限定したとき、即ち直並列グラフや部分k木に対して効率よいアルゴリズムを開発成功した。それらの成果を以下の論文でまとめた。1.Tomoya Fujino, Shuji Isobe, Xiao Zhou, and Takao Nishizaki Linear algorithm for finding list edge-colorings of series-parallel graphs IEICE Trans. on Information and Systems, E86-D(2003), pp.186-1902.Takehiro Ito, Takao Nishizaki, Xiao Zhou Algorithms for multicolorings of partial K-trees IEICE Trans. on Information and Systems, E86-D(2003), pp.191-200また、限定されたグラフに対して効率よいアルゴリズムや一般グラフに対して近似アルゴリズムや確率的アルゴリズム等の調査も行った。現在知られているアルゴリズムの理論的評価および計算機による実験的シミュレーションを行い、各手法によって得られるデータを分析した。また各手法の効率を理論と実験両方で検証した。

This year's most efficient communication systemム, 特にリスト辺色やmulti-color アルゴリズムを応与して研究开発を行なった. The リスト辺色やmultiple color problem is a generalization of the point color problem and the NP-hard problem. Generally speaking, the solution to the problem is the efficiency of the problem, and the efficiency of the problem is good. My 々はグラフのクラスをlimited したとき、that is, straight parallel グラフやPart of the wood に対してefficiencyよいアルゴリズムを开発successした.それらの Results are the following papers. 1.Tomoya Fujino, Shuji Isobe, Xiao Zhou, and Takao Nishizaki Linear algorithm for finding list edge-colorings of series-parallel graphs IEICE Trans. on Information and Systems, E86-D(2003), pp.186-1902.Takehiro Ito, Takao Nishizaki, Xiao Zhou Algorithms for multicolorings of partial K-trees IEICE Trans. on Information and Systems, E86-D(2003), pp.191-200また、limited version efficiency and efficiency Generally speaking, the accuracy of the survey is similar to the accuracy of the survey. Comments on the theory of the current knowledge of the computer science and technologyシミュレーションを行い, each technique によってgets られるデータをanalysisした. The efficiency of each method is based on the theory and the method is proved.

项目成果

T.Ito, T.Nishizaki, X.Zhou: "Algorithms for multicolorings of partial K-trees"IEICE Trans. on Information and Systems. E86-D. 191-200 (2003)

T.Ito、T.Nishizaki、X.Zhou：“部分 K 树的多色算法”IEICE Trans。

T.Nishizeki, J.Vygen, X.Zhou: "The edge-disjoint paths problem is NP-complete for series-parallel graphs"Discrete Applied Mathematics. 115. 177-186 (2001)

T.Nishizeki、J.Vygen、X.Zhou：“串并联图的边不相交路径问题是 NP 完全的”离散应用数学。

T.Fujino, S.Isobe, X.Zhou, T.Nishizaki: "Linear algorithm for finding list edge-colorings of series-parallel graphs"IEICE Trans. on Information and Systems. E86-D. 186-190 (2003)

T.Fujino、S.Isobe、X.Zhou、T.Nishizaki：“用于查找串并联图列表边缘着色的线性算法”IEICE Trans。

S.Isobe, X. Zhou, T.Nishizeki: "Total colorings of degenerated graphs"In Proc. of the 28th International Colloquium on Automata, Languages and Programming. LNCS, Springer. 2076. 506-517 (2001)

S.Isobe、X. Zhou、T.Nishizeki：“退化图的总着色”In Proc。

X.Zhou, T.Nishizeki: "Algorithm for the cost edge-coloring of trees"In Proc. of the 7th Mnnual International Conference on Computing and Combinatorics, LNCS, Springer. 2108. 288-297 (2001)

X.Zhou，T.Nishizeki：“树的成本边缘着色算法”在Proc。