Maximum renamable Horn sub-CNFs

Authors
Boros, E
Citation
E. Boros, Maximum renamable Horn sub-CNFs, DISCR APP M, 97, 1999, pp. 29-40
Citations number
27
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE APPLIED MATHEMATICS → ACNP
Volume
97
Year of publication
1999
Pages
29 - 40
Database
ISI
SICI code
Abstract
The NP-hard problem of finding the largest renamable Horn sub-CNF of a give n CNF is considered, and a polynomial time approximation algorithm is prese nted for this problem. It is shown that for cubic CNFs this algorithm has a guaranteed performance ratio of 40/67. (C) 1999 Elsevier Science B.V. All rights reserved.