Maximum renamable Horn sub-CNFs

DOI10.1016/S0166-218X(99)00031-1zbMath0941.68150OpenAlexW2056365656WikidataQ59560771 ScholiaQ59560771MaRDI QIDQ1961445

Endre Boros

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

zbMATH Keywords

polynomial time approximation algorithmHorn sub-CNF

Mathematics Subject Classification ID

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