An exact algorithm for the Boolean connectivity problem for k-CNF

DOI10.1007/978-3-642-14186-7_15MaRDI QIDQ4930587zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Publication date 29 September 2010

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

Full work available at URL https://doi.org/10.1007/978-3-642-14186-7_15

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• An exact algorithm for the Boolean connectivity problem for k-CNF
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

Cited in

(1)

• An exact algorithm for the Boolean connectivity problem for k-CNF

This page was built for publication: An exact algorithm for the Boolean connectivity problem for \(k\)-CNF

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