模式识别与人工智能
Thursday, Apr. 3, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2013, Vol. 26 Issue (7): 609-614    DOI:
Orignal Article Current Issue| Next Issue| Archive| Adv Search |
The Concept of Max-Flow and Its Properties in Dynamic Networks
ZHANG Ling
School of Computer Science and Technology,Anhui University,Hefei 230039

Download: PDF (379 KB)   HTML (0 KB) 
Export: BibTeX | EndNote (RIS)      
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.
Key wordsDynamic Network      Max-Flow      Steepest Flow      Min-Cut Theorem
7
     
Received: 24 April 2013     
ZTFLH: TP181  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
ZHANG Ling
Cite this article:   
ZHANG Ling. The Concept of Max-Flow and Its Properties in Dynamic Networks[J]. , 2013, 26(7): 609-614.
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2013/V26/I7/609
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn