20 citations · 75 across the 44 of their papers we have counts for
5 papers · 1 filter
Switchability and collapsibility of Gap Algebras
Barnaby Martin, Dmitriy Zhuk
Let A be an idempotent algebra on a 3-element domain D that omits a G-set for a factor. Suppose A is not αβ-projective (for some alpha, beta subsets of D) and is not collapsible. I…
The packing chromatic number of the infinite square lattice is between 13 and 15
Barnaby Martin, Franco Raimondi, Taolue Chen +1
Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss…
Constraint Satisfaction Problems around Skolem Arithmetic
Christian Glasser, Peter Jonsson, Barnaby Martin
We study interactions between Skolem Arithmetic and certain classes of Constraint Satisfaction Problems (CSPs). We revisit results of Glass er et al. in the context of CSPs and set…
Discrete Temporal Constraint Satisfaction Problems
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over $…
From complexity to algebra and back: digraph classes, collapsibility and the PGP
Catarina Carvalho, Florent Madelaine, Barnaby Martin
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…