Minesweeper on graphs

DOI10.1016/J.AMC.2011.01.046MaRDI QIDQ632908zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

consistencydynamic programmingtreewidthconstraint satisfactionCSPcounting problemgenerating polynomialsminesweeper

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(11)

• Treasure hunt in graph using pebbles
• scientific article; zbMATH DE number 7021370 (Why is no real title available?)
• 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 may not be NP-complete but is hard nonetheless
• `Minesweeper' and spectrum of discrete Laplacians

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)