TY - JOUR
ID - 85518
TI - Negative Cost Girth Problem using Map-Reduce Framework
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
Y1 - 2022
PY - 2022
VL -
IS -
SP - 1
EP - 20
KW - Map-Reduce
KW - Parallelism
KW - Negative Cost Girth
KW - Sequential
KW - Message Passing Interface
DO - 10.22059/jac.2022.85518
N2 - On 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.
UR - https://jac.ut.ac.ir/article_85518.html
L1 - https://jac.ut.ac.ir/article_85518_c101b52556cb22923c5ae7c1a2eeb043.pdf
ER -