کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434619 | 689769 | 2013 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On weight function methods in Chooser–Picker games
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study NP-hard Chooser–Picker biased games on hypergraphs and their connections to classic Maker–Breaker games. We prove two weight-function-based winning criteria for Picker and show that the Erdős–Selfridge winning criterion for Breaker’s win is also the winning criterion for Picker in (1:1) games. Thereby we improve previous results by Beck and by Csernenszky, Mándity and Pluhár. Moreover we estimate the critical bias for Picker in Chooser–Picker (1:q) games in which the aim of Chooser is to build a copy of a fixed size graph G in Kn.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 475, 4 March 2013, Pages 21-33
Journal: Theoretical Computer Science - Volume 475, 4 March 2013, Pages 21-33