سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات158
تعداد شماره‌ها6,243
تعداد مقالات67,879
تعداد مشاهده مقاله115,525,176
تعداد دریافت فایل اصل مقاله90,296,579
. (1400). Negative Cost Girth Problem using Map-Reduce Framework. , (), 1-20. doi: 10.22059/jac.2022.85518
. "Negative Cost Girth Problem using Map-Reduce Framework". , , , 1400, 1-20. doi: 10.22059/jac.2022.85518
. (1400). 'Negative Cost Girth Problem using Map-Reduce Framework', , (), pp. 1-20. doi: 10.22059/jac.2022.85518
. Negative Cost Girth Problem using Map-Reduce Framework. , 1400; (): 1-20. doi: 10.22059/jac.2022.85518

Negative Cost Girth Problem using Map-Reduce Framework

Journal of Algorithms and Computation
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 26 دی 1400    اصل مقاله (277.76 K)
شناسه دیجیتال (DOI): 10.22059/jac.2022.85518
چکیده
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.
کلیدواژه‌ها
Map-Reduce؛ Parallelism؛ Negative Cost Girth؛ Sequential؛ Message Passing Interface
آمار
تعداد مشاهده مقاله: 133
تعداد دریافت فایل اصل مقاله: 71


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب