摘要
动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。
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）.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第7期252-254,共3页
Computer Engineering
基金
国家安全基础研究基金资助重大项目(613610202)
关键词
动态容量网络
时间依赖网络
最小最大时间流
多项式算法
capacitated dynamic networks
time-dependent networks
rain max-time flow
polynomial algorithm
