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

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