Complexity and monotonicity results for domination games

DOI10.1016/J.TCS.2016.03.003zbMATH Open1338.68112OpenAlexW2294272868MaRDI QIDQ266262FDOQ266262

Authors Stephan Kreutzer, Sebastian Ordyniak

Publication date 13 April 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.03.003

zbMATH Keywords

monotonicitycops and robber gamesdomination search gamesgraph searching gamesparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Recommendations

• On the computational complexity of the domination game
• Complexity of the game domination problem
• On the dimension of simple monotonic games
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• On the complexity of iterated weak dominance in constant-sum games
• On the complexity of iterated weak dominance in constant-sum games
• On the Algorithmic Complexity of Total Domination
• On the complexity landscape of the domination chain
• Complexity of majority monopoly and signed domination problems
• Mathematical Foundations of Computer Science 2005

Cites work

• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• An annotated bibliography on guaranteed graph searching
• Distance \(d\)-domination games
• Eavesdropping games
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fundamentals of parameterized complexity
• Graph searching and a min-max theorem for tree-width
• On the domination search number
• On the structure of graphs with bounded asteroidal number
• Parametrized complexity theory.
• Searching and pebbling

Cited in

(6)

• On the domination search number
• scientific article; zbMATH DE number 1696531 (Why is no real title available?)
• Complexity of the game domination problem
• Approximation algorithms for domination search
• On the computational complexity of the domination game
• Distance \(d\)-domination games

This page was built for publication: Complexity and monotonicity results for domination games

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