动态网络中最大流快速增量求解
|
摘要
利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.
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.
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.
引文
[1]Goldberg A V.Recent developments in maximum flow algorithms(invited lecture)[C]//Proceedings of the6th Scandinavian Workshop on Algorithm Theory.Heidelber:Springer-Verlags,1988:1-10.
[2]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].2nd ed.Cambridge:M IT Press,2001:588-760.
[3]Ahuja R K,Magnanti T L,Orlin J B.Network flows:Theory,algorithms and applications[M].Upper Saddle River,NJ,USA:Prentice Hall Press,2005:294-356.
[4]Ford L R,Fulkerson D R.Flows in networks[M].Princeton,USA:Princeton University Press,1962:1-96.
[5]Edmonds J,Karp R M.Theoretical improvements in algorithm efficiency for netw orks flow problems[J].Journal of the ACM,1972,19(2):248-264.DOI:10.1145/321694.321699.
[6]Goldberg A V,Rao S.Beyond the flow decomposition barrier[J].Journal of the ACM,1998,45(5):783-797.DOI:10.1145/290179.290181.
[7]张宪超,万颖瑜,陈国良.一类实际网络中的最小截算法[J].软件学报,2003,14(5):885-890.Zhang Xianchao,Wan Yingyu,Chen Guoliang.Approaches to the minimum cut problem in a class of practical netw orks[J].Journal of Software,2003,14(5):885-890.(in Chinese)
[8]张宪超,江贺,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):543-551.Zhang Xianchao,Jiang He,Chen Guoliang.M inimum cuts and maximum flow s in directed planar netw orks w ith both node and edge capacities[J].Chinese Journal of Computers,2006,29(4):543-551.(in Chinese)
[9]Lee Y T,Rao S,Srivastava N.A new approach to computing maximum flow s using electrical flow s[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing.Palo Alto,CA,USA,2013:755-764.DOI:10.1145/2488608.2488704.
[10]Daitch S I,Spielman D A.Faster approximate lossy generalized flow via interior point algorithms[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing.Victoria,BC,Canada,2008:451-460.DOI:10.1145/1374376.1374441.
[11]Peng R.Approximate undirected maximum flows in O(M polylog(n))time[C]//Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms.Arlington,VA,USA,2016:1862-1867.DOI:10.1137/1.9781611974331.ch130.
[12]Zhao S,Xu X S,Hua B.Contraction network for solving maximum flow problem[C]//Proceedings of the ACM SIG KDD Workshop on Mining Data Semantics.Beijing,China,2012:1-6.DOI:10.1145/2350190.2350198.
[13]Sharma M,Ghosh D.Speeding up the estimation of the expected value of maximum flow through reliable netw orks[J].IEEE Transactions on Reliability,2013,62(1):105-115.DOI:10.1109/tr.2013.2241132.
[14]Hadji M,Zeghlache D.Minimum cost maximum flow algorithm for dynamic resource allocation in clouds[C]//IEEE International Conference on Cloud Computing.Honolulu,Haw aii,USA,2012:876-882.DOI:10.1109/cloud.2012.36.
[15]Szymanski T H.Achieving minimum-routing-cost maximum-flow s in infrastructure w ireless mesh netw orks[C]//IEEE Wireless Communications&Networking Conference.Paris,France,2012:2031-2036.DOI:10.1109/w cnc.2012.6214124.
[16]Bora N,Arora S,Arora N.An efficient algorithm for calculating maximum bipartite matching in a graph[J].International Journal of Advanced Computer Research,2013,3(10):193-199.
[17]Gu T L,Chang L,Xu Z B.A novel symbolic algorithm for mximum w eighted matching in bipartite graphs[J].International Journal of Comunications,Network and System Sciences,2012,4(2):111-121.DOI:10.4236/ijcns.2011.42014.
[18]Zhao P X,Zhang X.A survey on reliability evaluation of stochastic-flow netw orks in terms of minimal paths[C]//International Conference on Information Engineering&Computer Science.Wuhan,China,2009:2010-2013.DOI:10.1109/iciecs.2009.5365424.
[19]Jane C C,Lin J S,Yuan J.Reliability evaluation of a limited-flow netw ork in terms of minimal cutsets[J].IEEE Transactions on Reliability,1993,42(3):354-361,368.DOI:10.1109/24.257817.
[20]蔡伟,张柏礼,吕建华.不确定图最可靠最大流算法研究[J].计算机学报,2012,35(11):2371-2380.DOI:10.3724/SP.J.1016.2012.02371.Cai Wei,Zhang Baili,LüJianhua.Algorithms of the most reliable maximum flow on uncertain graph[J].Chinese Journal of Computers,2012,35(11):2371-2380.DOI:10.3724/SP.J.1016.2012.02371.(in Chinese)
[21]张铃.动态网络上最大流概念及其性质的研究[J].模式识别与人工智能,2013,26(7):609-614.DOI:10.3969/j.issn.1003-6059.2013.07.001.Zhang Ling.The concept of max-flow and its properties in dynamic netw orks[J].Pattern Recognition and Artificial Intelligence,2013,26(7):609-614.DOI:10.3969/j.issn.1003-6059.2013.07.001.(in Chinese)
[22]Kas M,Wachs M,Carley K M,et al.Incremental algorithm for updating betw eenness centrality in dynamically grow ing netw orks[C]//International Conference on Advances in Social Networks Analysis&Mining.Niagara Falls,Canada,2013:33-40.DOI:10.1145/2492517.2492533.
[23]Ben-Eliyahu-Zohary R.An incremental algorithm for generating all minimal models[J].Artificial Intelligence,2005,169(1):1-22.DOI:10.1016/j.artint.2005.06.003.
[24]Hsieh M C,Lee Y S,Yen S J.An efficient incremental algorithm for mining Web traversal patterns[C]//IEEE International Conference on E-business.Beijing,China,2005:274-281.
[25]Klingman D,Napier A,Stutz J.NETNEN:A program for generating large scale capacitated assignment,transportation and minimal cost flow netw ork problems[J].Management Science,1974,20(5):814-821.DOI:10.1287/mnsc.20.5.814.
[26]Johnson D B.Finding all the elementary circuits of a directed graph[J].SIAM Journal on Computing,1975,4(1):77-84.DOI:10.1137/0204007.
[2]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].2nd ed.Cambridge:M IT Press,2001:588-760.
[3]Ahuja R K,Magnanti T L,Orlin J B.Network flows:Theory,algorithms and applications[M].Upper Saddle River,NJ,USA:Prentice Hall Press,2005:294-356.
[4]Ford L R,Fulkerson D R.Flows in networks[M].Princeton,USA:Princeton University Press,1962:1-96.
[5]Edmonds J,Karp R M.Theoretical improvements in algorithm efficiency for netw orks flow problems[J].Journal of the ACM,1972,19(2):248-264.DOI:10.1145/321694.321699.
[6]Goldberg A V,Rao S.Beyond the flow decomposition barrier[J].Journal of the ACM,1998,45(5):783-797.DOI:10.1145/290179.290181.
[7]张宪超,万颖瑜,陈国良.一类实际网络中的最小截算法[J].软件学报,2003,14(5):885-890.Zhang Xianchao,Wan Yingyu,Chen Guoliang.Approaches to the minimum cut problem in a class of practical netw orks[J].Journal of Software,2003,14(5):885-890.(in Chinese)
[8]张宪超,江贺,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):543-551.Zhang Xianchao,Jiang He,Chen Guoliang.M inimum cuts and maximum flow s in directed planar netw orks w ith both node and edge capacities[J].Chinese Journal of Computers,2006,29(4):543-551.(in Chinese)
[9]Lee Y T,Rao S,Srivastava N.A new approach to computing maximum flow s using electrical flow s[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing.Palo Alto,CA,USA,2013:755-764.DOI:10.1145/2488608.2488704.
[10]Daitch S I,Spielman D A.Faster approximate lossy generalized flow via interior point algorithms[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing.Victoria,BC,Canada,2008:451-460.DOI:10.1145/1374376.1374441.
[11]Peng R.Approximate undirected maximum flows in O(M polylog(n))time[C]//Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms.Arlington,VA,USA,2016:1862-1867.DOI:10.1137/1.9781611974331.ch130.
[12]Zhao S,Xu X S,Hua B.Contraction network for solving maximum flow problem[C]//Proceedings of the ACM SIG KDD Workshop on Mining Data Semantics.Beijing,China,2012:1-6.DOI:10.1145/2350190.2350198.
[13]Sharma M,Ghosh D.Speeding up the estimation of the expected value of maximum flow through reliable netw orks[J].IEEE Transactions on Reliability,2013,62(1):105-115.DOI:10.1109/tr.2013.2241132.
[14]Hadji M,Zeghlache D.Minimum cost maximum flow algorithm for dynamic resource allocation in clouds[C]//IEEE International Conference on Cloud Computing.Honolulu,Haw aii,USA,2012:876-882.DOI:10.1109/cloud.2012.36.
[15]Szymanski T H.Achieving minimum-routing-cost maximum-flow s in infrastructure w ireless mesh netw orks[C]//IEEE Wireless Communications&Networking Conference.Paris,France,2012:2031-2036.DOI:10.1109/w cnc.2012.6214124.
[16]Bora N,Arora S,Arora N.An efficient algorithm for calculating maximum bipartite matching in a graph[J].International Journal of Advanced Computer Research,2013,3(10):193-199.
[17]Gu T L,Chang L,Xu Z B.A novel symbolic algorithm for mximum w eighted matching in bipartite graphs[J].International Journal of Comunications,Network and System Sciences,2012,4(2):111-121.DOI:10.4236/ijcns.2011.42014.
[18]Zhao P X,Zhang X.A survey on reliability evaluation of stochastic-flow netw orks in terms of minimal paths[C]//International Conference on Information Engineering&Computer Science.Wuhan,China,2009:2010-2013.DOI:10.1109/iciecs.2009.5365424.
[19]Jane C C,Lin J S,Yuan J.Reliability evaluation of a limited-flow netw ork in terms of minimal cutsets[J].IEEE Transactions on Reliability,1993,42(3):354-361,368.DOI:10.1109/24.257817.
[20]蔡伟,张柏礼,吕建华.不确定图最可靠最大流算法研究[J].计算机学报,2012,35(11):2371-2380.DOI:10.3724/SP.J.1016.2012.02371.Cai Wei,Zhang Baili,LüJianhua.Algorithms of the most reliable maximum flow on uncertain graph[J].Chinese Journal of Computers,2012,35(11):2371-2380.DOI:10.3724/SP.J.1016.2012.02371.(in Chinese)
[21]张铃.动态网络上最大流概念及其性质的研究[J].模式识别与人工智能,2013,26(7):609-614.DOI:10.3969/j.issn.1003-6059.2013.07.001.Zhang Ling.The concept of max-flow and its properties in dynamic netw orks[J].Pattern Recognition and Artificial Intelligence,2013,26(7):609-614.DOI:10.3969/j.issn.1003-6059.2013.07.001.(in Chinese)
[22]Kas M,Wachs M,Carley K M,et al.Incremental algorithm for updating betw eenness centrality in dynamically grow ing netw orks[C]//International Conference on Advances in Social Networks Analysis&Mining.Niagara Falls,Canada,2013:33-40.DOI:10.1145/2492517.2492533.
[23]Ben-Eliyahu-Zohary R.An incremental algorithm for generating all minimal models[J].Artificial Intelligence,2005,169(1):1-22.DOI:10.1016/j.artint.2005.06.003.
[24]Hsieh M C,Lee Y S,Yen S J.An efficient incremental algorithm for mining Web traversal patterns[C]//IEEE International Conference on E-business.Beijing,China,2005:274-281.
[25]Klingman D,Napier A,Stutz J.NETNEN:A program for generating large scale capacitated assignment,transportation and minimal cost flow netw ork problems[J].Management Science,1974,20(5):814-821.DOI:10.1287/mnsc.20.5.814.
[26]Johnson D B.Finding all the elementary circuits of a directed graph[J].SIAM Journal on Computing,1975,4(1):77-84.DOI:10.1137/0204007.