A Parallel Genetic Algorithm for Maximum Flow Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 6
Abstract
The maximum flow problem is a type of network optimization problem in the flow graph theory. Many important applications used the maximum flow problem and thus it has been studied by many researchers using different methods. Ford Fulkerson algorithm is the most popular algorithm that used to solve the maximum flow problem, but its complexity is high. In this paper, a parallel Genetic algorithm is applied to find a maximum flow in a weighted directed graph, by finding the objective function value for each augmenting path from the source to the sink simultaneously in the parallel steps in every iteration. The algorithm is implemented using Message Passing Interface (MPI) library, and results are conducted from a real distributed system IMAN1 supercomputer and were compared with a sequential version of Genetic-Maxflow. The simulation results show this parallel algorithm speedup the running time by achieving up to 50% parallel efficiency.
Authors and Affiliations
Ola M. Surakhi, Mohammad Qatawneh, Hussein A. al Ofeishat
Keywords
Related Articles
- EP ID EP259542
- DOI 10.14569/IJACSA.2017.080620
- Views 101
- Downloads 0
Analysis of Software Tools for Longitudinal Studies in Psychology
Longitudinal studies allow to access the review of causal hypotheses directly. It means that they make possible causal relation between the order of impacts (i.e. life events, educational effects, etc.) and the consequen...
A Readiness Evaluation of Applying e-Government in the Society: Shall Citizens begin to Use it?
As people are in the era of the web, most of the society is using networks in their daily task, governments had found, it is crucial to build an electronic entity that was named e-government, to make transactions easier...
No-Reference Perceived Image Quality Algorithm for Demosaiced Images
Visual image quality assessment (IQA) plays a key role in every multimedia application, as end user to it is a human-being. Real time applications demand no reference (NR) IQA, due to unavailability of the reference imag...
A Solution for the Uniform Integration of Field Devices in an Industrial Supervisory Control and Data Acquisition System
Supervisory Control and Data Acquisition (SCADA) systems are increasingly used solutions for monitoring and controlling various industrial processes. The existence of a large number of communication protocols helps to de...
A Mixed Method Study for Investigating Critical Success Factors (CSFs) of E-Learning in Saudi Arabian Universities
Electronic Learning (E-Learning) in the education system has become the obvious choice of the community over the globe because of its numerous advantages. The main aim of the present study is to identify Critical Success...