| 树状网络中最短接通时间的快速算法 |
| |
| 引用本文： | 陈勇,胡爱群,钟子果.树状网络中最短接通时间的快速算法[J].东南大学学报(自然科学版),2004,34(1):1-4. |
| |
| 作者姓名： | 陈勇 胡爱群 钟子果 |
| |
| 作者单位： | 东南大学无线电工程系,南京,210096 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划)，教育部优秀青年教师资助计划 |
| |
| 摘 要： | 针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n).
|
| 关 键 词： | 文件分配问题 接通时间 计算机网络 边着色 |
| 文章编号： | 1001-0505(2004)01-0001-04 |
| 修稿时间： | 2003年4月11日 |
Fast algorithm for calculating the minimum makespan in tree-type networks |
| |
| 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. |
| |
| Authors: | Chen Yong Hu Aiqun Zhong Ziguo |
| |
| 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. |
| |
| Keywords: | file allocation problem makespan computer networks edge coloring |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
