Complexity and monotonicity results for domination games

DOI10.1016/j.tcs.2016.03.003zbMath1338.68112OpenAlexW2294272868MaRDI QIDQ266262

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

monotonicityparameterized complexitycops and robber gamesdomination search gamesgraph searching games

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• An annotated bibliography on guaranteed graph searching
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• On the domination search number
• Searching and pebbling
• Parametrized complexity theory.
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Eavesdropping games
• Distance d-Domination Games
• On the structure of graphs with bounded asteroidal number