کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876074 | 689682 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The problem of finding the minimum cut of an undirected unweighted graph is studied on the external memory model. First, a lower bound of Ω((E/V)Sort(V)) on the number of I/Os is shown for the problem, where V is the number of vertices and E is the number of edges. Then the following are presented, (1) a deterministic minimum cut algorithm that usesO(minâ¡{c7(log3+ϵâ¡E)(MST(V,E)),c(logâ¡E)(MST(V,E))+(V/M)Sort(V)}) I/Os; here ϵ>0 is a small constant, MST(V,E) is the number of I/Os needed to compute a minimum spanning tree of the graph, and c is the value of the minimum cut. The algorithm performs better on dense graphs than the algorithm of [1], which requires O(E+c2Vlogâ¡(V/c)) I/Os, when executed on the external memory model. For a δ-fat graph (for δ>0, the maximum tree packing of the graph is at least (1+δ)c/2), our algorithm computes a minimum cut in O(c(logâ¡E)MST(V,E)) I/Os. (2) A randomized algorithm that computes minimum cut with high probability in O(c(logâ¡E)â
MST(V,E)+Sort(E)log2â¡V+VBSort(V)logâ¡V) I/Os. (3) A (2+ϵ)-minimum cut algorithm that requires O((E/V)MST(V,E)) I/Os.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 575, 13 April 2015, Pages 33-41
Journal: Theoretical Computer Science - Volume 575, 13 April 2015, Pages 33-41
نویسندگان
Alka Bhushan, G. Sajith,