Minesweeper on graphs

DOI10.1016/J.AMC.2011.01.046zbMATH Open1208.91027OpenAlexW2070641010MaRDI QIDQ632908FDOQ632908

Authors: Shahar Golan 

Publication date: 28 March 2011

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2011.01.046

Recommendations

• Minesweeper may not be NP-complete but is hard nonetheless
• Hyperbolic Minesweeper is in P
• A phase transition in Minesweeper
• Luckless graphical minesweeper
• The Minesweeper Game: Percolation and Complexity

zbMATH Keywords

consistencydynamic programmingtreewidthconstraint satisfactionCSPcounting problemgenerating polynomialsminesweeper

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Combinatorial games (91A46)

Cites Work

• Title not available (Why is that?)
• Graph minors. II. Algorithmic aspects of tree-width
• Treewidth. Computations and approximations
• Graph minors. I. Excluding a forest
• Minesweeper is NP-complete.
• How cellular automaton plays minesweeper
• `Minesweeper' and spectrum of discrete Laplacians
• Equal moments division of a set
• The Minesweeper Game: Percolation and Complexity
• Littlewood polynomials with high order zeros

Cited In (11)

• Treasure hunt in graph using pebbles
• Title not available (Why is that?)
• On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
• Minesweeper strategy for one mine
• The Minesweeper Game: Percolation and Complexity
• Luckless graphical minesweeper
• A phase transition in Minesweeper
• Hyperbolic Minesweeper is in P
• Application of spectral theory to constructing a puzzle on the basis of the Minesweeper computer game
• `Minesweeper' and spectrum of discrete Laplacians
• Minesweeper may not be NP-complete but is hard nonetheless

This page was built for publication: Minesweeper on graphs

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