Search Results

Documents authored by Kullmann, Oliver


Document
SAT Interactions (Dagstuhl Seminar 12471)

Authors: Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)


Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 12471 "SAT Interactions". The seminar brought together researchers from different areas from theoretical computer science as well as the area of SAT solvers. A key objective of the seminar has been to initiate or consolidate discussions among the different groups for a fresh attack on one of the most important problems in theoretical computer science and mathematics.

Cite as

Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer. SAT Interactions (Dagstuhl Seminar 12471). In Dagstuhl Reports, Volume 2, Issue 11, pp. 87-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{creignou_et_al:DagRep.2.11.87,
  author =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  title =	{{SAT Interactions (Dagstuhl Seminar 12471)}},
  pages =	{87--101},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.87},
  URN =		{urn:nbn:de:0030-drops-39786},
  doi =		{10.4230/DagRep.2.11.87},
  annote =	{Keywords: satisfiability problem, computational complexity, P-NP question, proof complexity, combinatorics, SAT-solvers, quantified Boolean formulas}
}
Document
Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities

Authors: Oliver Kullmann

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
Generalised CNFs are considered using such literals, which exclude exactly one possible value from the domain of the variable. First we consider poly-time SAT decision (and fixed-parameter tractability) exploiting matching theory. Then we consider irredundant generalised CNFs, and characterise some extremal minimally unsatisfiable CNFs.

Cite as

Oliver Kullmann. Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{kullmann:DagSemProc.06401.4,
  author =	{Kullmann, Oliver},
  title =	{{Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities}},
  booktitle =	{Complexity of Constraints},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.4},
  URN =		{urn:nbn:de:0030-drops-8030},
  doi =		{10.4230/DagSemProc.06401.4},
  annote =	{Keywords: Signed CNF, autarkies, minimal unsatisfiable, hypergraph colouring, block designs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail