On the Boolean Connectivity Problem for Horn Relations

DOI10.1007/978-3-540-72788-0_20MaRDI QIDQ3612466zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Publication date 10 March 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-72788-0_20

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical propositional logic (03B05) Connectivity (05C40) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the Boolean connectivity problem for Horn relations
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• A computational trichotomy for connectivity of Boolean satisfiability
• On relations satisfying some Horn formulas
• Combinatorial Problems for Horn Clauses
• On the structure of solution-graphs for Boolean formulas
• An exact algorithm for the Boolean connectivity problem for k-CNF

Cited in

(5)

• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the Boolean connectivity problem for Horn relations
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

This page was built for publication: On the Boolean Connectivity Problem for Horn Relations

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