Minimal unsatisfiability and minimal strongly connected digraphs

DOI10.1007/978-3-319-94144-8_20MaRDI QIDQ1656590zbMATH OpenOpenAlexFDO

Authors Hoda Abbasizanjani, Oliver Kullmann

Publication date 10 August 2018

Full work available at URL https://doi.org/10.1007/978-3-319-94144-8_20

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Recommendations

• On subclasses of minimal unsatisfiable formulas
• Complexity results on minimal unsatisfiable formulas
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• The complexity of some subclasses of minimal unsatisfiable formulas.

Cited in

(4)

• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
• Equivalence of strongly connected graphs and black-and-white 2-SAT problems
• Classes of hard formulas for QBF resolution

This page was built for publication: Minimal unsatisfiability and minimal strongly connected digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1656590)