Computational aspects of monotone dualization: a brief survey

DOI10.1016/j.dam.2007.04.017zbMath1160.68016OpenAlexW1976127067WikidataQ59259620 ScholiaQ59259620MaRDI QIDQ943839

Thomas Eiter, Georg Gottlob, Kazuhisa Makino

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.04.017

zbMATH Keywords

combinatorial enumerationtransversalshypergraphsdualizationself-dualitymonotone Boolean functionsindependent setslimited nondeterminismhitting setsoutput-polynomial algorithmspolynomial-total timequasi-polynomial timeset coverings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Boolean functions (06E30)

Related Items

Influence decision models: from cooperative game theory to social network analysis ⋮ An algorithm for solving parametric integer program ⋮ Semantic forgetting in answer set programming ⋮ On the Boolean connectivity problem for Horn relations ⋮ Optimal resource allocation enables mathematical exploration of microbial metabolic configurations ⋮ Multidimension: a dimensionality extension of simple games ⋮ Immune sets in monotone infection rules. Characterization and complexity ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ On the generalized dimension and codimension of simple games ⋮ Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ On the complexity of enumerating pseudo-intents ⋮ Counting minimal transversals of \(\beta\)-acyclic hypergraphs ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ Counting Minimal Dominating Sets ⋮ Counting or producing all fixed cardinality transversals ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Dualization in lattices given by ordered sets of irreducibles ⋮ Complexity of simplicial homology and independence complexes of chordal graphs ⋮ Dualization of Boolean functions using ternary decision diagrams ⋮ An algebraic algorithm for solving parametric integer programs ⋮ A study on monotone self-dual Boolean functions ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ Translating between the representations of a ranked convex geometry ⋮ Masking patterns in sequences: A new class of motif discovery with don't cares ⋮ Computing the output distribution and selection probabilities of a stack filter from the DNF of its positive Boolean function ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Dualization in lattices given by implicational bases ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ Linear separation of connected dominating sets in graphs ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Unnamed Item ⋮ Multiple hypernode hitting sets and smallest two-cores with targets ⋮ Implementing Efficient All Solutions SAT Solvers ⋮ An average study of hypergraphs and their minimal transversals

Cites Work

• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• An incremental method for generating prime implicants/implicates
• The computation of hitting sets: Review and new algorithms
• Dualization of regular Boolean functions
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An O(m n) algorithm for regular set-covering problems
• A theory of diagnosis from first principles
• On generating all maximal independent sets
• A correction to the algorithm in Reiter's theory of diagnosis
• Learning conjunctions of Horn clauses
• Double Horn functions
• Dualization, decision lists and identification of monotone discrete functions
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• On the frequency of the most frequently occurring variable in dual monotone DNFs
• On maximal frequent and minimal infrequent sets in binary matrices
• An inequality for polymatroid functions and its applications.
• A variant of Reiter's hitting-set algorithm
• Almost all monotone Boolean functions are polynomially learnable using membership queries
• Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• An SE-tree-based prime implicant generation algorithm
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Bidual Horn functions and extensions
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Queries and concept learning
• Complexity of identification and dualization of positive Boolean functions
• Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
• Minimizing the Average Query Complexity of Learning Monotone Boolean Functions
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
• New results on monotone dualization and generating hypergraph transversals
• On one criterion of the optihality of an algorithm for evaluating monotonic boolean functions
• A theory of the learnable
• A fast parallel algorithm for the maximal independent set problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• ON THE TWO-COLOURING OF HYPERGRAPHS
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithms for inferring functional dependencies from relations
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions
• A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
• Generating dual-bounded hypergraphs
• NP-completeness: A retrospective
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On the optimal evaluation of monotonic Boolean functions
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Parameterized and Exact Computation
• Algorithm Theory - SWAT 2004
• Covering Problems: Duality Relations and a New Method of Solution
• A New Algorithm for Generating Prime Implicants
• Computing and Combinatorics
• Algorithms - ESA 2003
• Advances in Artificial Intelligence
• LATIN 2004: Theoretical Informatics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item