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

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

 آمار

تعداد نشریات158
تعداد شماره‌ها6,225
تعداد مقالات67,685
تعداد مشاهده مقاله114,998,834
تعداد دریافت فایل اصل مقاله89,673,219
Shamsi, Mahboubeh, Rasouli Kenari, Abdolreza, Aghamohammadi, Roghayeh. (1400). Negative Cost Girth Problem using Map-Reduce Framework. , 53(2), 173-196. doi: 10.22059/jac.2021.85375
Mahboubeh Shamsi; Abdolreza Rasouli Kenari; Roghayeh Aghamohammadi. "Negative Cost Girth Problem using Map-Reduce Framework". , 53, 2, 1400, 173-196. doi: 10.22059/jac.2021.85375
Shamsi, Mahboubeh, Rasouli Kenari, Abdolreza, Aghamohammadi, Roghayeh. (1400). 'Negative Cost Girth Problem using Map-Reduce Framework', , 53(2), pp. 173-196. doi: 10.22059/jac.2021.85375
Shamsi, Mahboubeh, Rasouli Kenari, Abdolreza, Aghamohammadi, Roghayeh. Negative Cost Girth Problem using Map-Reduce Framework. , 1400; 53(2): 173-196. doi: 10.22059/jac.2021.85375

Negative Cost Girth Problem using Map-Reduce Framework

Journal of Algorithms and Computation
دوره 53، شماره 2، اسفند 2021، صفحه 173-196    اصل مقاله (486.01 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2021.85375
نویسندگان
Mahboubeh Shamsi؛ Abdolreza Rasouli Kenari* ؛ Roghayeh Aghamohammadi
Faculty of Electrical and Computer Engineering, Qom University of Technology, Qom, Iran
چکیده
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
آمار
تعداد مشاهده مقاله: 215
تعداد دریافت فایل اصل مقاله: 104


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