39 citations · 161 across the 21 of their papers we have counts for
22 papers
A SAT Encoding for the -Fractions Problem
Michael Codish
This note describes a SAT encoding for the -fractions puzzle which is problem 041 of the CSPLib. Using a SAT solver we obtain a solution for two of the six remaining open instan…
Graphs with girth at least 5 with orders between 20 and 32
Alice Miller, Michael Codish
We prove properties of extremal graphs of girth 5 and order 20 <=v <= 32. In each case we identify the possible minimum and maximum degrees, and in some cases prove the existence o…
Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)
Michael Frank, Michael Codish
This paper presents the plnauty~library, a Prolog interface to the nauty graph-automorphism tool. Adding the capabilities of nauty to Prolog combines the strength of the "generate…
Breaking Symmetries in Graph Search with Canonizing Sets
Avraham Itzhakov, Michael Codish
There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of th…
Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking
Michael Codish, Michael Frank, Avraham Itzhakov +1
The number is often presented as the unknown Ramsey number with the best chances of being found "soon". Yet, its precise value has remained unknown for almost 50 years.…
When Six Gates are Not Enough
Michael Codish, Luís Cruz-Filipe, Michael Frank +1
We apply the pigeonhole principle to show that there must exist Boolean functions on 7 inputs with a multiplicative complexity of at least 7, i.e., that cannot be computed with onl…