کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950808 | 1441036 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The game total domination problem is log-complete in PSPACE
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper, we continue the study of the total domination game in graphs introduced in Henning et al. (2015) [10]. A vertex totally dominates another vertex in a graph G if they are neighbors. A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S. The total domination game played on G consists of two players, named Dominator and Staller, who alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. The game ends when the set of vertices chosen becomes a total dominating set in G. Dominator wishes to end the game with a minimum number of vertices chosen, and Staller wishes to end the game with as many vertices chosen as possible. The game total domination number of G is the number of vertices chosen when Dominator starts the game and both players play optimally. In this paper, we show that verifying whether the game total domination number of a graph is bounded by a given integer is log-complete in PSPACE.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 126, October 2017, Pages 12-17
Journal: Information Processing Letters - Volume 126, October 2017, Pages 12-17
نویسندگان
Boštjan Brešar, Michael A. Henning,