Maximum renamable Horn sub-CNFs

Endre Boros

doi:10.1016/S0166-218X(99)00031-1

Back

Journal article

Open access

Peer reviewed

Maximum renamable Horn sub-CNFs

Endre Boros

Discrete Applied Mathematics, Vol.96, pp.29-40

1999

DOI: https://doi.org/10.1016/S0166-218X(99)00031-1

Abstract

Approximation algorithms

Horn CNF

Satisfiability

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 .

Files and links (1)

url

https://doi.org/10.1016/S0166-218X(99)00031-1View

Version of Record (VoR) Open

Metrics

8 Record Views

7 Times Cited - Web of Science

Details

Title: Maximum renamable Horn sub-CNFs
Creators: Endre Boros - RUTCOR, Rutgers-State University of NJ, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA
Publication Details: Discrete Applied Mathematics, Vol.96, pp.29-40
Date published: 1999
Publisher: Elsevier B.V
Academic Unit: Management Science and Information Systems (RBS)
Language: English
Resource Type: Journal article
Identifiers: 991031666074004646