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 98
- Downloads 0
Clustering Analysis of Wireless Sensor Network Based on Network Coding with Low-Density Parity Check
The number of nodes in wireless sensor networks (WSNs) is one of the fundamental parameters when it comes to developing an algorithm based on Network Coding (NC) with LDPC (Low Density Parity Check) code because it direc...
Smart Transportation Application using Global Positioning System
Significant increase is noticed in the utilization of mobile applications for different purposes in the past decade. These applications can improve any individual’s way of life in many aspects such as communication, coll...
Evaluation of Fault Tolerance in Cloud Computing using Colored Petri Nets
Nowadays, the necessity of rendering reliable services to the customers in business markets is assumed as a crucial matter for the service providers, and the importance of this subject in many fields is undeniable. Desig...
Smoothness Measure for Image Fusion in Discrete Cosine Transform
The aim of image fusion is to generate high-quality images using information from source images. The fused image contains more information than any of the source images. Image fusion using transforms is more effective th...
Design of ANFIS Estimator of Permanent Magnet Brushless DC Motor Position for PV Pumping System
This paper presents a new scheme for PMBLDC (permanent magnet brushless direct current) rotor position estimation based an ANFIS (adaptive network fuzzy inference system) estimator. The operation of such motor requires a...