3 papers
cs.CC2026
Maximum independent queen set on polyominoes is NP-complete
Alexis Langlois-Rémillard, Mia Müßig
Finding a set of vertices in a graph with no edges between them, INDSET, is a well-known NP-complete problem. The queen graph of a chessboard is constructed by taking vertices as t…
math.HO2026
Extremal fences with polyforms
Alexis Langlois-Rémillard, Mia N. Müßig, Érika Roldán
We present results around an isoperimetric problem built on polyforms: What is the biggest enclosed area one can build using polyforms in each of the three plane tessellations? We…
math.CO2022
Complexity of chess domination problems
Alexis Langlois-Rémillard, Mia Müßig, Érika Róldan
We study different domination problems of attacking and non-attacking rooks and queens on polyominoes and polycubes of all dimensions. Our main result proves that maximum independe…