Resolution based algorithms for the transversal hypergraph generation problem

DOI10.1016/J.TCS.2020.02.033zbMath1436.05080OpenAlexW3009653673MaRDI QIDQ2310740

Lina Panagopoulou, Dimitris J. Kavvadias, Stavros S. Cosmandakis

Publication date: 6 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.02.033

zbMATH Keywords

monotone Boolean functionspolynomial spacehypergraph dualizationminimal transversalBoolean resolution

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85) Boolean functions (06E30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating all maximal models of a Boolean expression
• Towards NP-P via proof complexity and search
• Version spaces and the consistency problem
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Horn axiomatizations for sequential data
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• On generating all maximal independent sets
• The complexity of model checking for circumscriptive formulae
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• On maximal frequent and minimal infrequent sets in binary matrices
• Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Efficient algorithms for dualizing large-scale hypergraphs
• Complexity of identification and dualization of positive Boolean functions
• Reasoning with models
• Minimizing the Average Query Complexity of Learning Monotone Boolean Functions
• An Efficient Algorithm for the Transversal Hypergraph Generation
• A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• LATIN 2004: Theoretical Informatics
• Foundations of Information and Knowledge Systems

This page was built for publication: Resolution based algorithms for the transversal hypergraph generation problem