Maximum renamable Horn sub-CNFs

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The NP-hard problem of finding the largest renamable Horn sub-CNF of a given CNF is considered, and a polynomial time approximation algorithm is presented for this problem. It is shown that for cubic CNFs this algorithm has a guaranteed performance ratio of 40/67.

Original languageAmerican English
Pages (from-to)29-40
Number of pages12
JournalDiscrete Applied Mathematics
StatePublished - Oct 15 1999

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Approximation algorithms
  • Horn CNF
  • Satisfiability


Dive into the research topics of 'Maximum renamable Horn sub-CNFs'. Together they form a unique fingerprint.

Cite this