کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438493 | 690281 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounds on the bisection width for random d -regular graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random d-regular graphs, for any value of d. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of d-regular graphs. We provide bounds for 5≤d≤12. We also give empirical values of the size of the bisection found by the algorithm for some small values of d and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum bisection.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 382, Issue 2, 31 August 2007, Pages 120-130
Journal: Theoretical Computer Science - Volume 382, Issue 2, 31 August 2007, Pages 120-130