Incremental polynomial time dualization of quadratic functions and a subclass of degree-k functions

DOI10.1007/S10479-009-0637-XMaRDI QIDQ646712zbMATH OpenOpenAlexFDO

Authors Oya Ekin Karasan

Publication date 17 November 2011

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-009-0637-x

zbMATH Keywords

Boolean functiondegree-\(k\) functiondualizationhypergraph transversalpolynomial total time algorithmquadratic function

Mathematics Subject Classification ID

Boolean programming (90C09) Optimality conditions and duality in mathematical programming (90C46)

Recommendations

• Recognition and dualization of disguised bidual Horn functions.
• Computational aspects of monotone dualization: a brief survey
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• An O(nm)-time algorithm for computing the dual of a regular Boolean function
• Complexity of identification and dualization of positive Boolean functions

Cites work

• A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
• Algorithm Theory - SWAT 2004
• An O(nm)-time algorithm for computing the dual of a regular Boolean function
• Complexity of identification and dualization of positive Boolean functions
• Computational aspects of monotone dualization: a brief survey
• Double Horn functions
• Dual subimplicants of positive Boolean functions
• Dualization of regular Boolean functions
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Equational characterizations of Boolean function classes
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Horn functions and submodular Boolean functions
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 861622 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Polynomial-time inference of all valid implications for Horn and related formulae
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• Recognition and dualization of disguised bidual Horn functions.
• The Problem of Simplifying Truth Functions

Cited in

(5)

• An O(nm)-time algorithm for computing the dual of a regular Boolean function
• Recognition and dualization of disguised bidual Horn functions.
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• A duality between Boolean functions
• A study on monotone self-dual Boolean functions

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q646712)