AU - Klavzar, S.
AU - Kosmrlj, G.
AU - Schmidt, S.
TI - On the Computational Complexity of the Domination Game
PT - JOURNAL ARTICLE
TA - IJMSI
JN - IJMSI
VO - 10
VI - 2
IP - 2
4099 - http://ijmsi.ir/article-1-794-en.html
4100 - http://ijmsi.ir/article-1-794-en.pdf
SO - IJMSI 2
ABĀ - The domination game is played on an arbitrary graph $G$ by two players, Dominator and Staller. It is known that verifying whether the game domination number of a graph is bounded by a given integer $k$ is PSPACE-complete. On the other hand, it is showed in this paper that the problem can be solved for a graph $G$ in $mathcal O(Delta(G)cdot |V(G)|^k)$ time. In the special case when $k=3$ and the graph $G$ considered has maximum diameter, the complexity is improved to $mathcal O (|V(G)|cdot |E(G)|+Delta(G)^3)$.
CP - IRAN
IN -
LG - eng
PB - IJMSI
PG - 115
PT - Research paper
YR - 2015