Maximum renamable Horn sub-CNFs
type: Item
instance of: scholarly article
title: Maximum renamable Horn sub-CNFs
zbMATH Open document ID: 0941.68150
DOI: 10.1016/S0166-218X(99)00031-1
author: Endre Boros
published in: Discrete Applied Mathematics
publication date: 1999-01-01T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1389862
zbMATH Keywords: Horn sub-CNF
zbMATH Keywords: polynomial time approximation algorithm
Wikidata QID: Q59560771
MaRDI profile type: Publication
cites work: Q4230322
cites work: Recognizing disguised NR(1) instances of the satisfiability problem
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Polynomial-time inference of all valid implications for Horn and related formulae
cites work: A Complexity Index for Satisfiability Problems
cites work: Recognition of \(q\)-Horn formulae in linear time
cites work: Probabilistic bounds and algorithms for the maximum satisfiability problem
cites work: On renamable Horn and generalized Horn functions
cites work: Extended Horn sets in propositional logic
cites work: Detecting embedded Horn structure in propositional logic
cites work: Variable and term removal from Boolean formulae
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Polynomially solvable satisfiability problems
cites work: Algorithms for testing the satisfiability of propositional formulae
cites work: Q4198056
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: .878-approximation algorithms for MAX CUT and MAX 2SAT
cites work: Unification as a complexity measure for logic programming
cites work: Complete problems for deterministic polynomial time
cites work: Renaming a Set of Clauses as a Horn Set
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
full work available at URL: s0166-218x(99)00031-1
OpenAlex ID: W2056365656
DBLP publication ID: journals/dam/Boros99
description: scientific article; zbMATH DE number 1389862