Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
From MaRDI portal
Publication:646712
DOI10.1007/s10479-009-0637-xzbMath1225.90153OpenAlexW2141285440MaRDI QIDQ646712
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
dualizationquadratic functionBoolean functionhypergraph transversaldegree-\(k\) functionpolynomial total time algorithm
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Computational aspects of monotone dualization: a brief survey
- Dualization of regular Boolean functions
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- On generating all maximal independent sets
- Double Horn functions
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Polynomial-time inference of all valid implications for Horn and related formulae
- Horn functions and submodular Boolean functions
- Recognition and dualization of disguised bidual Horn functions.
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- Equational characterizations of Boolean function classes
- Complexity of identification and dualization of positive Boolean functions
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
- Algorithm Theory - SWAT 2004
- The Problem of Simplifying Truth Functions
This page was built for publication: Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
