کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648586 | 1342418 | 2009 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Threshold and complexity results for the cover pebbling game
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a configuration of pebbles on the vertices of a graph, a pebbling move is defined by removing two pebbles from some vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ(G)γ(G), is the smallest number of pebbles such that through a sequence of pebbling moves, a pebble can eventually be placed on every vertex simultaneously, no matter how the pebbles are initially distributed. We determine Bose–Einstein and Maxwell–Boltzmann cover pebbling thresholds for the complete graph. Also, we show that the cover pebbling decision problem is NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3609–3624
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3609–3624
نویسندگان
Anant P. Godbole, Nathaniel G. Watson, Carl R. Yerger,