Name
Abstract | ||
|---|---|---|
After providing a simple characterization of Horn functions (i.e., those Boolean functions that have a Horn DNF), we study in detail the special class of submodular functions. Every prime implicant of such a function involves at most one complemented and at most one uncomplemented variable, and based on this we give a one-to-one correspondence between submodular functions and partial preorders (reflexive and transitive binary relations), and in particular between the nondegenerate acyclic submodular functions and the partially ordered sets. There is a one-to-one correspondence between the roots of a submodular function and the ideals of the associated partial preorder. There is also a one-to-one correspondence between the prime implicants of the dual of the submodular function and the maximal antichains of the associated partial preorder. Based on these results, we give graph-theoretic characterizations for all minimum prime DNF representations of a submodular function. The problem of recognizing submodular functions in DNF representation is coNP-complete. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0304-3975(96)00202-2 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
horn function,submodular Boolean function | Journal | 175 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 9 |
PageRank | References | Authors |
0.58 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oya Ekin | 1 | 69 | 5.34 |
| Peter L. Hammer | 2 | 1996 | 288.93 |
| Uri N. Peled | 3 | 173 | 22.91 |