Complexity of chess domination problems

DOI10.1007/S40687-024-00492-5MaRDI QIDQ7015863zbMATH OpenFDO

Authors Alexis Langlois-Rémillard, Mia Müßig, Érika Roldán

Publication date 7 March 2025

Published in Research in the Mathematical Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S40687-024-00492-5

zbMATH Keywords

\(N\)-queens problemart gallery theoremcomputational geometrydomination problemguard numberlinear programmingNP-completionNP-hardnesspolyominovisibility coverage

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Computational aspects of satisfiability (68R07) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Linear programming (90C05)

Cites work

• A survey of known results and research areas for \(n\)-queens
• A unified approach to visibility representations of planar graphs
• An Application of Graph Theory and Integer Programming: Chessboard Non-Attacking Puzzles
• Art gallery problem with rook and queen vision
• Chasing first queens by integer programming
• Checker Boards and Polyominoes
• Complexity of n-queens completion
• Computational complexity of the r-visibility guard set problem for polyominoes
• Core-boosted linear search for incomplete MaxSAT
• Domination in chessboards
• Gauss and the eight queens problem: A study in miniature of the propagation of historical error
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• Mathematische Unterhaltungen und Spiele. Zweite, vermehrte und verbesserte Auflage. 2. Band. Mit 128 Figuren im Text.
• On maximal independent sets of vertices in claw-free graphs
• Parallelizing the dual revised simplex method
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• Reducibility among combinatorial problems
• Representing a planar graph by vertical lines joining different levels
• The \(n\)-queens completion problem
• The art gallery theorem for polyominoes
• Towards a theory of domination in graphs
• Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

This page was built for publication: Complexity of chess domination problems

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