|
|||||
|
|
| 动态容量网络中的最小最大时间流问题 | |
| 引用本文： | 庞博,谢政,陈挚,张军. 动态容量网络中的最小最大时间流问题[J]. 计算机工程, 2010, 36(7): 252-254 |
| 作者姓名： | 庞博 谢政 陈挚 张军 |
| 作者单位： | 1. 国防科技大学数学与系统科学系,长沙,410073 2. 北京航空航天大学电子信息工程学院,北京,100083 |
| 基金项目： | 国家安全基础研究基金资助重大项目(613610202) |
| 摘 要： | 动态(时间依赖的)容量网络与传统静态网络相比更具现实意义，在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上，研究具有实际背景的动态容量网络的最小最大时间流问题，给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例，其时间复杂度为O(mMv)。 |
| 关 键 词： | 动态容量网络 时间依赖网络 最小最大时间流 多项式算法 |
| 修稿时间： | |
Min Max-time Flow Problem in Capacitated Dynamic Networks |
|
| PANG Bo,XIE Zheng,CHEN Zhi,ZHANG Jun. Min Max-time Flow Problem in Capacitated Dynamic Networks[J]. Computer Engineering, 2010, 36(7): 252-254 | |
| Authors: | PANG Bo XIE Zheng CHEN Zhi ZHANG Jun |
| Affiliation: | (1. Department of Mathematics and System Science, National University of Defense Technology, Changsha 410073; 2. School of Electronics and Information Engineering, Beihang University, Beijing 100083) |
| Abstract: | The capacitated dynamic(time-dependent) networks are more realistic than the classical static networks, and are applicated to a wide range of fields including transportation, logistics and telecommunication network systems. Based on the shortest path algorithm in time-dependent networks, this paper studies the min max-time flow problem in capacitated dynamic networks with real background, and presents an algorithm to solve this problem. The running time complexity of this algorithm is in O(mMn). |
| Keywords: | capacitated dynamic networks time-dependent networks min max-time flow polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程》浏览原始摘要信息 | |
| 点击此处可从《计算机工程》下载免费的PDF全文 | |