The Minimal Hitting Set Generation Problem: Algorithms and Computation
From MaRDI portal
Publication:2953406
DOI10.1137/15M1055024zbMath1352.68279arXiv1601.02939OpenAlexW2964055388WikidataQ61714551 ScholiaQ61714551MaRDI QIDQ2953406
Paola Vera-Licona, Andrew Gainer-Dewar
Publication date: 4 January 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.02939
combinatorial algorithmshypergraph transversalset cover problemminimal hitting setBoolean dualization
Related Items (7)
Compressed representation of learning spaces ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Compression with wildcards: all exact or all minimal hitting sets ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Unnamed Item ⋮ Minimal winning coalitions and orders of criticality ⋮ Implementing Efficient All Solutions SAT Solvers
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames
- A global parallel algorithm for the hypergraph transversal problem
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Computational aspects of monotone dualization: a brief survey
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- The computation of hitting sets: Review and new algorithms
- Lower bounds for three algorithms for transversal hypergraph generation
- A theory of diagnosis from first principles
- On generating all maximal independent sets
- A correction to the algorithm in Reiter's theory of diagnosis
- On maximal frequent and minimal infrequent sets in binary matrices
- Minimal approximate hitting sets and rule templates
- A variant of Reiter's hitting-set algorithm
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Efficient algorithms for dualizing large-scale hypergraphs
- Reverse-engineering of polynomial dynamical systems
- Complexity of identification and dualization of positive Boolean functions
- There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- An Efficient Algorithm for the Transversal Hypergraph Generation
- Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
- 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
- Graph-Based Algorithms for Boolean Function Manipulation
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Monotone Boolean functions
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Experimental comparison of the two Fredman-Khachiyan-algorithms
- Left-to-Right Multiplication for Monotone Boolean Dualization
- A Lower Bound for the HBC Transversal Hypergraph Generation
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
- Computing and Combinatorics
This page was built for publication: The Minimal Hitting Set Generation Problem: Algorithms and Computation
