کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649848 | 1342467 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on coloring sparse random graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring G(n,p), Random Structures and Algorithms 24 (3) (2004) 259–278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability pp satisfying np≤1.01np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors Gn,pGn,p with the minimal number of colors and has expected linear running time, provided that np≤1.33np≤1.33.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3381–3384
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3381–3384
نویسندگان
Christian Sommer,