The game total domination problem is log-complete in PSPACE
From MaRDI portal
Publication:2361492
DOI10.1016/j.ipl.2017.05.007zbMath1409.68133OpenAlexW2617826600MaRDI QIDQ2361492
Boštjan Brešar, Michael A. Henning
Publication date: 30 June 2017
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2017.05.007
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
Paired-Domination Game Played in Graphs, Maker-breaker total domination game, Infinite families of circular and Möbius ladders that are total domination game critical, Domination game and minimal edge cuts, Effect of predomination and vertex removal on the game total domination number of a graph, Total connected domination game, Game total domination critical graphs, An Introduction to Game Domination in Graphs, Game total domination for cyclic bipartite graphs
Cites Work
- Game total domination for cycles and paths
- Complexity of the game domination problem
- The domination game played on unions of graphs
- Total version of the domination game
- On the game domination number of graphs with given minimum degree
- On the complexity of some two-person perfect-information games
- The 4/5 upper bound on the game total domination number
- Domination game played on trees and spanning subgraphs
- Domination game: effect of edge- and vertex-removal
- Realizations of the game domination number
- Domination game: extremal families of graphs for \(3/5\)-conjectures
- Progress towards the total domination game \(\frac{3}{4}\)-conjecture
- Transversal Game on Hypergraphs and the $\frac{3}{4}$-Conjecture on the Total Domination Game
- Domination Game and an Imagination Strategy
- Extremal Problems for Game Domination Number
