دانلود مقاله انگلیسی رایگان:الگوریتم درخت برش موازی - 2017
بلافاصله پس از پرداخت دانلود کنید
دانلود مقاله انگلیسی پردازش موازی رایگان
  • Parallel cut tree algorithms Parallel cut tree algorithms
    Parallel cut tree algorithms

    سال انتشار:

    2017


    عنوان انگلیسی مقاله:

    Parallel cut tree algorithms


    ترجمه فارسی عنوان مقاله:

    الگوریتم درخت برش موازی


    منبع:

    Sciencedirect - Elsevier - J: Parallel Distrib: Comput:, 109 (2017) 1-14: doi:10:1016/j:jpdc:2017:04:007


    نویسنده:

    Jaime Cohen a, Luiz A. Rodrigues b, Elias P. Duarte Jr. c,*


    چکیده انگلیسی:

    A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of vertices of an undirected graph. Cut trees solve the all pairs minimum s–t-cut problem efficiently. Cut trees have a large number of applications including the solution of important combinatorial problems in fields such as graph clustering and graph connectivity. They have also been applied to scheduling problems, social network analysis, biological data analysis, among others. Two sequential algorithms to compute a cut tree of a capacitated undirected graph are well known: the Gomory–Hu algorithm and the Gusfield algorithm. In this work three parallel cut tree algorithms are presented, including parallel versions of Gusfield and Gomory–Hu algorithms. A hybrid algorithm that combines techniques from both algorithms is proposed which provides a more robust performance for arbitrary instances. Experimental results show that the three algorithms achieve significant speedups on real and synthetic graphs. We discuss the trade-offs between the alternatives, each of which presents better results given the characteristics of the input graph. On several instances the hybrid algorithm outperformed both other algorithms, being faster than the parallel Gomory–Hu algorithm on most instances.
    Keywords: Graph edge-connectivity | Cut tree algorithms | Parallel algorithms


    سطح: متوسط
    تعداد صفحات فایل pdf انگلیسی: 14
    حجم فایل: 610 کیلوبایت

    قیمت: رایگان


    توضیحات اضافی:




اگر این مقاله را پسندیدید آن را در شبکه های اجتماعی به اشتراک بگذارید (برای به اشتراک گذاری بر روی ایکن های زیر کلیک کنید)

تعداد نظرات : 0

الزامی
الزامی
الزامی
rss مقالات ترجمه شده rss مقالات انگلیسی rss کتاب های انگلیسی rss مقالات آموزشی
logo-samandehi