On the complexity of the misère version of three games played on graphs
From MaRDI portal
(Redirected from On the complexity of the misère version of three games played on graphs)
Abstract: We investigate the complexity of finding a winning strategy for the mis`ere version of three games played on graphs : two variants of the game , introduced by Stockmann in 2004 and the game on both directed and undirected graphs. We show that on general graphs those three games are -Hard or Complete. For one -Hard variant of , we find an algorithm to compute an effective winning strategy in time when is a bipartite graph.
Recommendations
Cites work
Cited in
(10)- Undirected edge geography
- A Nim game played on graphs.
- Pirates and treasure
- A PSPACE-complete graph nim
- Strings-and-coins and Nimstring are PSPACE-complete
- Vertex Nim played on graphs
- Graph convexity impartial games: complexity and winning strategies
- The combinatorial game \textsc{Nofil} played on Steiner triple systems
- Geography, Kotzig's Nim, and variants
- Misère annihilation games
This page was built for publication: On the complexity of the misère version of three games played on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354773)