How Many Conflicts Does It Need to Be Unsatisfiable?

DOI10.1007/978-3-540-79719-7_23zbMath1138.68553OpenAlexW2158947586WikidataQ56475807 ScholiaQ56475807MaRDI QIDQ3502712

Dominik Scheder, Philipp Zumstein

Publication date: 27 May 2008

Published in: Theory and Applications of Satisfiability Testing – SAT 2008 (Search for Journal in Brave)

Full work available at URL: https://madoc.bib.uni-mannheim.de/41139/1/conflicts-postprint.pdf

zbMATH Keywords

satisfiabilityconflict graphunsatisfiable formulasLovász Local Lemma

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05)

Related Items (1)

New width parameters for SAT and \#SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lopsided Lovász Local lemma and Latin transversals
• Using Lovász local lemma in the space of random injections
• The complexity of facets resolved
• The size Ramsey number
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On subclasses of minimal unsatisfiable formulas
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Branching rules for satisfiability
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Theory and Applications of Satisfiability Testing

This page was built for publication: How Many Conflicts Does It Need to Be Unsatisfiable?