| Algorithm of capacity expansion on networks optimization |
| |
| 作者姓名： | YUShengsheng LIUYuhua MAOJingzhong XUKaihua |
| |
| 作者单位： | [1]CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,China; [2]DepartmentofMathematics,CentralChinaNormalUniversity,Wuhan430079,China [3]EducationalInformatizationResearchCenter,CentralChmaNormalUniversity,Wuhan430079,China |
| |
| 基金项目： | 国家自然科学基金，湖北省科研项目 |
| |
| 摘 要： | The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset are‘s group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks.
|
| 关 键 词： | 容量延伸网络 图论 网络优化 最优算法 最大流量 最小割集 标准法 Ford-Fulkerson算法 |
| 收稿时间： | 2003-01-27 |
Algorithm of capacity expansion on networks optimization |
| |
| YUShengsheng LIUYuhua MAOJingzhong XUKaihua.Algorithm of capacity expansion on networks optimization[J].Chinese Science Bulletin,2003,48(10):1048-1050. |
| |
| Authors: | Shengsheng?Yu Email author" target="_blank">Yuhua?LiuEmail author Jingzhong?Mao Kaihua?Xu |
| |
| Institution: | YU Shengsheng1, LIU Yuhua1,2, MAO Jingzhong3 & XU Kaihua4 1. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 2. Department of Computer Science, Central China Normal University, Wuhan 430079, China; 3. Department of Mathematics, Central China Normal University, Wuhan 430079, China 4. Educational Informatization Research Center, Central China Normal University, Wuhan 430079, China |
| |
| Abstract: | The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset arcs group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks. |
| |
| Keywords: | maximum flow minimum cutset capacity-expanded network optimization algorithm |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《中国科学通报(英文版)》浏览原始摘要信息 |
| 点击此处可从《中国科学通报(英文版)》下载免费的PDF全文 |
|
