|
|
|
| The Concept of Max-Flow and Its Properties in Dynamic Networks |
| ZHANG Ling |
| School of Computer Science and Technology,Anhui University,Hefei 230039 |
|
|
|
|
Abstract Based on the dynamic quotient space model,the definitions of the max-flow and min-cut,and the condition that min-cut theorem holds in dynamic networks,are investigated. The analysis of the characteristics of max-flow in dynamic networks shows if the max-flow concept in the static environment is simply transferred to the dynamic one,the transformed max-flow does not have the two main properties,i.e. the additivity and total flow maximization. By introducing the concept of t-cut networks,a dynamic network is transformed into the combination of a set of static networks. Therefore,a new definition of the max-flow (steepest flow) is proposed and the defined concept is proved to have the above two properties. Then,a corresponding min-cut concept is presented and it is proved that the min-cut theorem holds under the new concepts of max-flow and min-cut. Finally,the algorithm for computing dynamic max-flow (steepest flow) is given.
|
|
Received: 24 April 2013
|
|
|
|
|
|
[1] Zhang Ling,Zhang Bo. The Theory and Applications of Problem Solving. 2nd Edition. Beijing,China: Tsinghua University Press,2007 (in Chinese)
(张 铃,张 钹.问题求解理论及应用——商空间粒度计算理论及应用.第2版.北京:清华大学出版社,2007)
[2] Zhang Ling,Zhang Bo. Dynamic Quotient Space Model and Its Basic Properties. Pattern Recognition and Artificial Intelligence,2012,25(2): 181-185 (in Chinese)
(张 铃,张 钹.动态商空间模型及其基本性质.模式识别与人工智能,2012,25(2): 181-185)
[3] Ling Zhang,Fuqui He,Yanping Zhang,et al. A New Algorithm for Optimal Path Finding in Complex Networks Based on the Quotient Space. Fundamenta Informaticae,2009,93(4): 459-469
[4] He Fugui,Zhang Yanping,Chen Jie,et al. Path Queries on Massive Graphs Based on Multi-Granular Graph Partitioning // Proc of the 6th International Conference on Rough Sets and Knowledge Technology. Banf,Canada,2011: 569-578
[5] He Fugui,Zhang Yanping,Zhang Ling. Network Granular Storage and Its Application to Path finding. Computer Applications and Software,2011,28(11): 99-101 (in Chinese)
(何富贵,张燕平,张 铃.网络的粒度存储及在路径搜索中的应用.计算机应用与软件,2011,28(11): 99-101)
[6] Ford L R Jr,Fulkerson D R. Flows in Networks. Princeton,USA: Princeton University Press,1962
[7] Lu Kaicheng,Lu Huaming. The Graph Theory and Its Applications. Beijing,China: Tsinghua University Press,1995 (in Chinese)
(卢开澄,卢华明.图论及其应用.第2版. 北京:清华大学出版社,1995 ) |
|
|
|
2013, Vol. 26 
