Minimum dominating set of queens: a trivial programming exercise?

DOI10.1016/J.DAM.2009.09.019MaRDI QIDQ968146zbMATH OpenOpenAlexFDO

Authors Henning Fernau

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.09.019

zbMATH Keywords

exact algorithmsparameterized algorithmsdomination problems\(\mathcal {NP}\)-completenesschess problems

Mathematics Subject Classification ID

Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the independent queens covering problem
• On the queen domination problem
• Values of domination numbers of the queen's graph
• Computational methods and new results for chessboard problems
• scientific article; zbMATH DE number 1051284

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 683826 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 844149 (Why is no real title available?)
• A dynamic programming solution to the n-queens problem
• A partial k-arboretum of graphs with bounded treewidth
• A simplified solution of the n queens' problem
• Algorithms – ESA 2005
• An improved lower bound for domination numbers of the queen's graph
• An improved upper bound for queens domination numbers
• An upper bound for the minimum number of queens covering the \(n {\times} n\) chessboard
• Chessboard domination problems
• Domination by queens on a square beehive
• Easy problems for tree-decomposable graphs
• Independence for knights on hexagon and triangle boards
• Mixed Search Number of Permutation Graphs
• Mixed searching and proper-path-width
• On Exact Algorithms for Treewidth
• On bounds for a board covering problem
• On the Fast Searching Problem
• On the independent queens covering problem
• SOFSEM 2005: Theory and Practice of Computer Science
• The vertex separation number of a graph equals its path-width
• Treewidth. Computations and approximations
• Values of domination numbers of the queen's graph

Cited in

(5)

• Domination of the rectangular queen's graph
• scientific article; zbMATH DE number 93505 (Why is no real title available?)
• All paths lead to Rome
• Domination in chessboards
• My top 10 graph theory conjectures and open problems

This page was built for publication: Minimum dominating set of queens: a trivial programming exercise?

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