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 74
- Downloads 0
An Adaptive Intrusion Detection Method for Wireless Sensor Networks
Current intrusion detection systems for Wireless Sensor Networks (WSNs) which are usually designed to detect a specific form of intrusion or only applied for one specific type of network structure has apparently restrict...
Arabic Sentiment Analysis: A Survey
Most social media commentary in the Arabic language space is made using unstructured non-grammatical slang Arabic language, presenting complex challenges for sentiment analysis and opinion extraction of online commentary...
A Novel Neural Network Based Method Developed for Digit Recognition Applied to Automatic Speed Sign Recognition
This Paper presents a new hybrid technique for digit recognition applied to the speed limit sign recognition task. The complete recognition system consists in the detection and recognition of the speed signs in RGB image...
Universal Learning System for Embedded System Education and Promotion
In this article, the idea of the universal learning system for embedded systems is presented. The proposed system provides a complete learning environment consisting of the information collection center, preference estim...
Estimating Evapotranspiration using Machine Learning Techniques
The measurement of evapotranspiration is the most important factor in irrigation scheduling. Evapotranspiration means loss of water from the surface of plant and soil. Evaporation parameters are being used in studying wa...