کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654346 | 1632821 | 2009 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Does the lit-only restriction make any difference for the σσ-game and σ+σ+-game?
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Each vertex in a simple graph is in one of two states: “on” or “off”. The set of all on vertices is called a configuration. In the σσ-game, “pushing” a vertex vv changes the state of all vertices in the open neighborhood of vv, while in the σ+σ+-game pushing vv changes the state of all vertices in its closed neighborhood. The reachability question for these two games is to decide whether a given configuration can be reached from a given starting configuration by a sequence of pushes. We consider the lit-only restriction on these two games where a vertex can be pushed only if it is in the on state. We show that the lit-only restriction can make a big difference for reachability in the σσ-game, but has essentially no effect in the σ+σ+-game.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 30, Issue 4, May 2009, Pages 774–787
Journal: European Journal of Combinatorics - Volume 30, Issue 4, May 2009, Pages 774–787
نویسندگان
John Goldwasser, Xinmao Wang, Yaokun Wu,