On Horn envelopes and hypergraph transversals
| Author(s) : | Martha Sideri Dimitris Kavvadias, |
| Publisher : | N/A |
| Publication Date : | 1993 |
| ISSN : | N/A |
| Abstract : | Abstract: We study the problem of bounding from above and below a given set of bit vectors by the set of satisfying truth assignments of a Horn formula. We point out a rather unexpected connection between the upper bounding problem and the problem of generating all transversals of a hypergraph, and settle several related complexity questions. 1., |