Maximum renamable Horn sub-CNFs
From MaRDI portal
Publication:1961445
DOI10.1016/S0166-218X(99)00031-1zbMath0941.68150OpenAlexW2056365656WikidataQ59560771 ScholiaQ59560771MaRDI QIDQ1961445
Publication date: 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00031-1
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
On the size of maximum renamable Horn sub-CNF ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Pseudo-Boolean optimization ⋮ Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances ⋮ Covering non-uniform hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Polynomially solvable satisfiability problems
- Detecting embedded Horn structure in propositional logic
- Complete problems for deterministic polynomial time
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Recognition of \(q\)-Horn formulae in linear time
- Polynomial-time inference of all valid implications for Horn and related formulae
- On renamable Horn and generalized Horn functions
- Variable and term removal from Boolean formulae
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Unification as a complexity measure for logic programming
- Algorithms for testing the satisfiability of propositional formulae
- Recognizing disguised NR(1) instances of the satisfiability problem
- On the Complexity of Timetable and Multicommodity Flow Problems
- Renaming a Set of Clauses as a Horn Set
- A Complexity Index for Satisfiability Problems
- Extended Horn sets in propositional logic
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
