# [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] 点击复制 树状网络中最短接通时间的快速算法() 分享到： var jiathis_config = { data_track_clickback: true };

34

2004年第1期

1-4

2004-01-20

## 文章信息/Info

Title:
Fast algorithm for calculating the minimum makespan in tree-type networks

Author(s):
Department of Radio Engineering, Southeast University, Nanjing 210096, China

Keywords:

TP393.01
DOI:
10.3969/j.issn.1001-0505.2004.01.001

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.