Detecting embedded Horn structure in propositional logic
From MaRDI portal
Publication:1198035
DOI10.1016/0020-0190(92)90098-GzbMath0780.68055MaRDI QIDQ1198035
Publication date: 16 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
NP-hard; maximum clique problem; set packing problem; propositional satisfiability problem; maximum renamable Horn problem
Related Items
Variable and term removal from Boolean formulae, Recognizing renamable generalized propositional Horn formulas is NP- complete, Testing heuristics: We have it all wrong, Maximum renamable Horn sub-CNFs, Mixed logical-linear programming
Cites Work
- Unnamed Item
- An exact algorithm for the maximum clique problem
- On renamable Horn and generalized Horn functions
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Finding a Maximum Clique in an Arbitrary Graph
- Recognizing disguised NR(1) instances of the satisfiability problem