On the Boolean Connectivity Problem for Horn Relations
DOI10.1007/978-3-540-72788-0_20zbMATH Open1214.03026OpenAlexW1741233485MaRDI QIDQ3612466FDOQ3612466
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
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
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)
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)
