Horn functions and submodular Boolean functions

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

zbMATH Keywords

antichainssubmodular functionsHorn functionsDNF representationspartial preorderspatially ordered sets

Mathematics Subject Classification ID

Partial orders, general (06A06) Boolean functions (06E30)

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