Horn functions and submodular Boolean functions
From MaRDI portal
Publication:1392203
DOI10.1016/S0304-3975(96)00202-2zbMath0895.06008OpenAlexW2080957551MaRDI QIDQ1392203
Uri N. Peled, Peter L. Hammer, Oya Ekin
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00202-2
antichainssubmodular functionsHorn functionsDNF representationspartial preorderspatially ordered sets
Related Items
Disjunctive analogues of submodular and supermodular pseudo-Boolean functions, Generating all maximal models of a Boolean expression, Submodular Functions: Learnability, Structure, and Optimization, Union-closed sets and Horn Boolean functions, Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions, Bidual Horn functions and extensions, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, Double Horn functions, Recognition and dualization of disguised bidual Horn functions.
Cites Work
- Unnamed Item
- Unnamed Item
- On generating all maximal independent sets
- Horn functions and their DNFs
- On the notion of balance of a signed graph
- A Way to Simplify Truth Functions
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Recognizing disguised NR(1) instances of the satisfiability problem