AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

On the Implementation of Goldberg's Maximum flow Algorithm in Extended Mixed Network


Affiliations
1 University of Danang, Danang, Viet Nam
2 Vinaphone of Danang, Viet Nam
3 College of Transport II, Ministry of Transport, Viet Nam
 

In this paper, we solve this problem of finding maximum flow in extended mixed network by Revised preflow-push methods of Goldberg This algorithm completely different algorithm postflow-pull in [15]. However, we share some common theory with [15].

Keywords

Algorithm, Maximum Flow, Extended Mixed Network, Preflow, Excess.
User
Notifications
Font Size

  • Chien Tran Quoc. Postflow-pull methods to find maximal flow. Journal of science and technology University of DaNang, 5(40), 31-38, 2010.

  • L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

  • J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, vol. 19, no. 2, pp. 248–264, 1972.

  • A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Proceedings of the eighteenth annual ACM symposium on Theory of computing. New York, NY, USA: ACM, pp. 136146, 1986.

  • Robert Sedgewick. Algorithms in C Part 5: Graph Algorithms. Addison-Wesley, 2001.

  • R. J. Anderson and a. C. S. Jo. On the parallel implementation of goldberg’s maximum flow algorithm. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM, pp. 168–177, 1992.

  • D. Bader and V. Sachdeva. A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic. Proceedings of the 18th ISCA International Conference on Parallel and Distributed Computing Systems, 2005.

  • B. Hong. A lock-free multi-threaded algorithm for the maximum flow problem. IEEE International Parallel and Distributed Processing Symposium, 2008.

  • Zhengyu He, Bo Hong. Dynamically Tuned Push-Relabel Algorithm for the Maximum Flow Problem on CPU-GPU-Hybrid Platforms. School of Electrical and Computer Engineering-Georgia Institute of Technology, 2010.

  • Chien Tran Quoc, Lau Nguyen Dinh, Trinh Nguyen Thi Tu. Sequential and Parallel Algorithm by Postflow-Pull Methods to Find Maximum Flow. Proceedings 2013 13th International Conference on Computational Science and Its Applications, pp 178-181, 2013.

  • Lau Nguyen Dinh, Thanh Le Manh, Chien Tran Quoc. Sequential and Parallel Algorithm by Pre-Push Methods to Find Maximum Flow. Vietnam Academy of Science and Technology AND Posts & Telecommunications Institute of Technology, special issue works Electic, Tel, IT; 51(4A) pp 109125, 2013.

  • Lau Nguyen Dinh, Chien Tran Quoc and Manh Le Thanh. Parallel algorithm to divide optimal linear flow on extended traffic network. Research, Development and Application on Information & Communication Technology, Ministry of Information & Communication of Vietnam, No 3, V-1, 2014.

  • Naveen Garg, Jochen Könemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput, Canada, 37(2), pp. 630-652, 2007.

  • Lau Nguyen Dinh, Chien Tran Quoc, Thanh Le Manh.. Improved Computing Performance for Algorithm Finding the Shortest Path in Extended Graph. proceedings of international conference on foundations of computer science (FCS’14), pp 14-20, 2014.

  • Nguyen Dinh Lau, Tran Quoc Chien, Sequential and parallel Algorithm to find maximum flow on extended mixed networks by revised postflow-pull methods, Fourth International Conference on Advanced Information Technologies and Applications (ICAITA 2015), ISSN: 2231–5403, ISBN: 978-1-921987-43-4, DOI: 10.5121/csit.2015.51501, 2015, pp. 19-28


Abstract Views: 237

PDF Views: 120




  • On the Implementation of Goldberg's Maximum flow Algorithm in Extended Mixed Network

Abstract Views: 237  |  PDF Views: 120

Authors

Nguyen Dinh Lau
University of Danang, Danang, Viet Nam
Tran Quoc Chien
University of Danang, Danang, Viet Nam
Phan Phu Cuong
Vinaphone of Danang, Viet Nam
Le Hong Dung
College of Transport II, Ministry of Transport, Viet Nam

Abstract


In this paper, we solve this problem of finding maximum flow in extended mixed network by Revised preflow-push methods of Goldberg This algorithm completely different algorithm postflow-pull in [15]. However, we share some common theory with [15].

Keywords


Algorithm, Maximum Flow, Extended Mixed Network, Preflow, Excess.

References