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

DOI10.1007/s10479-009-0637-xzbMath1225.90153OpenAlexW2141285440MaRDI QIDQ646712

Oya Ekin Karaşan

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

dualizationquadratic functionBoolean functionhypergraph transversaldegree-\(k\) functionpolynomial total time algorithm

Mathematics Subject Classification ID

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

Related Items (1)

A study on monotone self-dual Boolean functions

Uses Software

• JBool

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