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