دوره 10، شماره 2 - ( 7-1394 )                   جلد 10 شماره 2 صفحات 115-122 | برگشت به فهرست نسخه ها



DOI: 10.7508/ijmsi.2015.02.011

XML Print


Download citation:
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-fa.html
On the Computational Complexity of the Domination Game. مجله علوم ریاضی و انفورماتیک ایرانیان. 1394; 10 (2) :115-122

URL: http://ijmsi.ir/article-1-794-fa.html


چکیده:  

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)$.

نوع مطالعه: پژوهشي | موضوع مقاله: عمومى

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
کد امنیتی را در کادر بنویسید

کلیه حقوق این وب سایت متعلق به نشریه علوم ریاضی و انفورماتیک می باشد.

طراحی و برنامه نویسی : یکتاوب افزار شرق

© 2015 All Rights Reserved | Iranian Journal of Mathematical Sciences and Informatics

Designed & Developed by : Yektaweb