Title :
An improved algorithm for solving maximum flow problem
Author :
Zhao, Lifeng ; Meng, Xiaowan
Author_Institution :
Sch. of Sci., Nanjing Univ. of Posts & Telecommun., Nanjing, China
Abstract :
There are lots of steps and complicated calculation in the existing algorithm for solving the maximum flow,and because of improper selection order of augmented path, we cannot obtain the ideal maximum flow. In order to solve these problems in existing algorithm, this paper make some improvement of the existing algorithms, then puts forward a new improved algorithm for solving the maximum flow problem which make use of divide area and the degree of vertex. And it is verified that the improved algorithm is effective and intuitive through the concrete example, and avoid the labeling process, the entire operation process only needs drawing a diagram to be completed.
Keywords :
graph theory; network theory (graphs); transportation; augmented path; diagram drawing; divide area; graph theory; improper selection order; maximum flow problem; network flow theory; vertex degree; Algorithm design and analysis; Computers; Concrete; Educational institutions; Graph theory; Labeling; Telecommunications; augmenting path; degree; divide area; maximum flow;
Conference_Titel :
Natural Computation (ICNC), 2012 Eighth International Conference on
Conference_Location :
Chongqing
Print_ISBN :
978-1-4577-2130-4
DOI :
10.1109/ICNC.2012.6234734