203 citations · 322 across the 18 of their papers we have counts for
19 papers
Simple minimally unsatisfiable subsets of 2-CNFs
Oliver Kullmann, Edward Clewer
We present a study of minimal unsatisfiable subsets (MUSs) of 2-CNF Boolean formulas, building on the Abbasizanjani-Kullmann classification of minimally unsatisfiable 2-CNFs (2-MUs…
The classification of minimally unsatisfiable 2-CNFs -- a fundamental study
Hoda Abbasizanjani, Oliver Kullmann
Conjunctive normal forms where every clause has length at most two are called 2-CNFs. We study minimally unsatisfiable 2-CNFs (2-MUs), that is, unsatisfiable 2-CNFs where removing…
Minimal unsatisfiability and deficiency: recent developments
Oliver Kullmann
Starting with Aharoni and Linial in 1986, the deficiency delta(F) = c(F) - n(F) >= 1 for minimally unsatisfiable clause-sets F, the difference of the number of clauses and the numb…
Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
Marijn J. H. Heule, Oliver Kullmann, Victor W. Marek
The boolean Pythagorean Triples problem has been a longstanding open problem in Ramsey Theory: Can the set N = of natural numbers be divided into two parts, such th…
Unsatisfiable hitting clause-sets with three more clauses than variables
Oliver Kullmann, Xishun Zhao
The topic of this paper is the Finiteness Conjecture for minimally unsatisfiable clause-sets (MUs), stating that for each fixed deficiency (number of clauses minus number of variab…
Computing maximal autarkies with few and simple oracle queries
Oliver Kullmann, Joao Marques-Silva
We consider the algorithmic task of computing a maximal autarky for a clause-set F, i.e., a partial assignment which satisfies every clause of F it touches, and where this property…