On the computational complexity of the domination game

MaRDI QIDQ2800503zbMATH OpenFDO

Authors Sandi Klavžar, Gašper Košmrlj, Simon Schmidt

Publication date 15 April 2016

Published in Iranian Journal of Mathematical Sciences and Informatics (Search for Journal in Brave)

Full work available at URL http://www.ijmsi.ir/browse.php?slc_lang=en&sid=1&a_id=794

zbMATH Keywords

domination gamegame domination numbercomplexity of algorithms

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Recommendations

• Complexity of the game domination problem
• The game total domination problem is log-complete in PSPACE
• Extremal problems for game domination number
• Complexity and monotonicity results for domination games
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two

Cited in

(11)

• Complexity and monotonicity results for domination games
• Complexity of the game domination problem
• The game total domination problem is log-complete in PSPACE
• Restricted Power - Computational Complexity Results for Strategic Defense Games
• Domino Games and Complexity
• The complexity of free-flood-it on \(2\times n\) boards
• Further progress on the heredity of the game domination number
• On the Complexity of n-Player Hackenbush
• An introduction to game domination in graphs
• scientific article; zbMATH DE number 3876591 (Why is no real title available?)
• Domination and signed domination number of Cayley graphs

This page was built for publication: On the computational complexity of the domination game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800503)