东南大学学报（自然科学版）2017，Vol.47Issue(3)：450-455,6.DOI:10.3969/j.issn.1001-0505.2017.03.006
动态网络中最大流快速增量求解
Fast incremental maximum flow algorithm in dynamic network
摘要
Abstract
An maximum flow incremental algorithm based on augmented routing tree (MFIA _ ART) was proposed to obtain augmenting paths directly without complex calculation.The algorithm cached the simple path information during calculating the original network maximum flow.When network topology changing,the augmenting path was obtained from the cache data,rather than through complex calculation in residual network.In addition,to avoid traversing invalid simple paths including saturated edges,an augmented routing tree was proposed to index all simple paths.Using the tree,the next augmenting paths could be sequentially found by traversing from root to leaf to achieve maximum flow.The time complexity is determined by the height of ART,it was far less than the augmenting path number thus improving the algorithm performance.Experimental results show that MFIA_ ART in time performance has a greater advantage than Dinic algorithm,and it is especially suitable for sparse graph.关键词
最大流/增量算法/增广路径选择树/简单路径Key words
maximum flow/incremental algorithm/augmented routing tree/simple path分类
信息技术与安全科学引用本文复制引用
张柏礼,王媛瑗,洪亮,田伟,吕建华..动态网络中最大流快速增量求解[J].东南大学学报（自然科学版）,2017,47(3):450-455,6.基金项目
国家自然科学基金资助项目(61300200,61232007,61073059). （61300200,61232007,61073059）
