با سلام خدمت کاربران در صورتی که با خطای سیستم پرداخت بانکی مواجه شدید از طریق کارت به کارت (6037997535328901 بانک ملی ناصر خنجری ) مقاله خود را دریافت کنید (تا مشکل رفع گردد).
ردیف | عنوان | نوع |
---|---|---|
1 |
Parallel cut tree algorithms
الگوریتم درخت برش موازی-2017 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 |
مقاله انگلیسی |