[1]陈勇,胡爱群,钟子果.树状网络中最短接通时间的快速算法[J].东南大学学报(自然科学版),2004,34(1):1-4.[doi:10.3969/j.issn.1001-0505.2004.01.001]
 Chen Yong,Hu Aiqun,Zhong Ziguo.Fast algorithm for calculating the minimum makespan in tree-type networks[J].Journal of Southeast University (Natural Science Edition),2004,34(1):1-4.[doi:10.3969/j.issn.1001-0505.2004.01.001]
点击复制

树状网络中最短接通时间的快速算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
34
期数:
2004年第1期
页码:
1-4
栏目:
计算机科学与工程
出版日期:
2004-01-20

文章信息/Info

Title:
Fast algorithm for calculating the minimum makespan in tree-type networks
作者:
陈勇 胡爱群 钟子果
东南大学无线电工程系, 南京 210096
Author(s):
Chen Yong Hu Aiqun Zhong Ziguo
Department of Radio Engineering, Southeast University, Nanjing 210096, China
关键词:
文件分配问题 接通时间 计算机网络 边着色
Keywords:
file allocation problem makespan computer networks edge-coloring
分类号:
TP393.01
DOI:
10.3969/j.issn.1001-0505.2004.01.001
摘要:
针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n).
Abstract:
Focusing on the file allocation problem, a computationally efficient algorithm for calculating the minimum makespan in tree-type networks is proposed. In our approach, the original network is decomposed into a set of smaller subnetworks to be processed, based on the concept of edge coloring and numbering combined with network topology. It is shown that the optimal solution for subnetworks is close to the optimal solution of the original network. Theoretical analysis shows the computational complexity of the proposed algorithm is O(n)while the precision of the minimum makespan declined is insignificant. Numerical experiments corroborate the obtained theoretical results.

参考文献/References:

[1] Chu W W.Optimal file allocation in a multiple computer system [J].IEEE Trans Computers,1969,18(10):885-889.
[2] Lee L W,Scheuermann P,Vingralek R.File assignment in parallel I/O systems with minimal variance of service time[J].IEEE Trans Computers,2000,49(2):127-140.
[3] Chang P Y,Chen D J,Kavi K M.Multimedia file allocation on VC networks using multipath routing [J].IEEE Trans Computers,2000,49(9):971-977.
[4] Cidon I,Kutten S,Soffer R.Optimal allocation of electronic content [J]. Computer Networks,2002,40(2):205-218.
[5] 宋增民.图论及其应用[M].南京:东南大学出版社,1997.11,187.

备注/Memo

备注/Memo:
基金项目: 国家高技术研究发展计划(863计划)资助项目(2002AA143010,2003AA143040)、教育部优秀青年教师资助计划项目.
作者简介: 陈勇(1976—),男,博士生,channely@vip.sina.com; 胡爱群(联系人),男,博士,教授,博士生导师,aqhu@seu.edu.cn.
更新日期/Last Update: 2004-01-20