University of TehranJournal of Algorithms and Computation2476-277653220211201Negative Cost Girth Problem using Map-Reduce Framework1731968537510.22059/jac.2021.85375ENMahboubeh ShamsiFaculty of Electrical and Computer Engineering, Qom University of Technology, Qom, Iran0000-0003-1238-4315Abdolreza Rasouli KenariFaculty of Electrical and Computer Engineering, Qom University of Technology, Qom, Iran0000-0003-4817-9380Roghayeh AghamohammadiFaculty of Electrical and Computer Engineering, Qom University of Technology, Qom, IranJournal Article20220105On a graph with a negative cost cycle, the shortest path is undefined, but the number of edges of the shortest negative cost cycle could be computed. It is called Negative Cost Girth (NCG). The NCG problem is applied in many optimization issues such as scheduling and model verification. The existing polynomial algorithms suffer from high computation and memory consumption. In this paper, a powerful Map-Reduce framework implemented to find the NCG of a graph. The proposed algorithm runs in $O(\log_{}{k})$ parallel time over $O(n^3)$ on each Hadoop nodes, where $n, k$ are the size of the graph and the value of NCG, respectively. The Hadoop implementation of the algorithm shows that the total execution time is reduced by 50\% compared with polynomial algorithms, especially in large networks concerning increasing the numbers of Hadoop nodes. The result proves the efficiency of the approach for solving the NCG problem to process big data in a parallel and distributed way.https://jac.ut.ac.ir/article_85375_6ccd81357666d14addd94c017d2d98d1.pdf