Volume 10, Issue 2 (10-2015)
IJMSI 2015, 10(2): 115-122 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Klavzar S, Kosmrlj G, Schmidt S. On the Computational Complexity of the Domination Game. IJMSI 2015; 10 (2) :115-122
URL: http://ijmsi.ir/article-1-794-en.html
URL: http://ijmsi.ir/article-1-794-en.html
Abstract:
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)$.
Type of Study: Research paper |
Subject:
General
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
