این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
Iranian Journal of Mathematical Sciences and Informatics، جلد ۱۰، شماره ۲، صفحات ۱۱۵-۱۲۲
عنوان فارسی
چکیده فارسی مقاله
کلیدواژه‌های فارسی مقاله
عنوان انگلیسی On the Computational Complexity of the Domination Game
چکیده انگلیسی مقاله 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)$.
کلیدواژه‌های انگلیسی مقاله
نویسندگان مقاله s klavzar | s. klavzar


g kosmrlj | g. kosmrlj


s schmidt | s. schmidt


نشانی اینترنتی http://www.ijmsi.ir/browse.php?a_code=A-10-583-8&slc_lang=en&sid=en
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده en
موضوعات مقاله منتشر شده عمومی
نوع مقاله منتشر شده پژوهشی
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات