Kullmann, Oliver
Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities
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.
BibTeX - Entry
@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/opus/volltexte/2006/803},
URN = {urn:nbn:de:0030-drops-8030},
doi = {10.4230/DagSemProc.06401.4},
annote = {Keywords: Signed CNF, autarkies, minimal unsatisfiable, hypergraph colouring, block designs}
}
|
Keywords: |
|
Signed CNF, autarkies, minimal unsatisfiable, hypergraph colouring, block designs |
|
Seminar: |
|
06401 - Complexity of Constraints
|
|
Issue date: |
|
2006 |
|
Date of publication: |
|
15.11.2006 |
15.11.2006
