On the computational complexity of the domination game

zbMATH Open1334.05089MaRDI QIDQ2800503FDOQ2800503

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

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

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)

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
• Title not available (Why is that?)
• 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)