DagSemProc.06401.4.pdf
- Filesize: 0.68 MB
- 70 pages
Document
Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6401
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-15
Cite As Get BibTex
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)
https://doi.org/10.4230/DagSemProc.06401.4
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.
Subject Classification
Keywords
- Signed CNF
- autarkies
- minimal unsatisfiable
- hypergraph colouring
- block designs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads