Publish Date : 28th December, 2017
It is pleasure to let you know that three BSCSE undergraduate students Fahim Shahriar, Aakib BinNesar, Naweed Mohammad Mahbub has won the Best Student Paper award for their paper titled “An Enhanced Genetic Algorithm for Producing Efficient Graph Partitions” at the 4th International Conference on Networking, Systems and Security (4th NSysS 2017 https://cse.buet.ac.bd/nsyss2017-4th/). The paper is an outcome of their undergraduate research work done under the supervision of Dr. Swakkhar Shatabda. The award was USD 200 with certificates and crest.
Graph partitioning is a well-known problem which has varied applications such as scientific computing, distributed computing, social network analysis, task scheduling in multi-processor systems, data mining and many other domains. In this paper, we introduce EGAGP, an enhanced genetic algorithm for producing efficient graph partitions. Keeping real world applications in mind, our algorithm takes into account the capacity limitations of individual partitions to ensure balanced partitioning. This approach enables various applications for this algorithm, the most significant of which is in mobile cloud computing. Our algorithm can be used in efficient deployment of software components in cloud architecture as it is efficient and fast and it also ensures feasibility by only allowing partition sizes up to the designated limits. We achieved faster calculation time by applying methods to calculate graph cut size faster. Our approach of dividing the total calculation time among primary and secondary populations proved to produce better quality results. Our proposed method tested on standard benchmark dataset, produces feasible and good quality results and outperforms the state-of-the-art methods in terms of time and quality of the partitions.