Identifying the Minimal Transversals of a Hypergraph and Related Problems

DOI10.1137/S0097539793250299zbMATH Open0842.05070MaRDI QIDQ4862797

Publication date: 28 July 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

databases hitting sets hypergraph transversal hypergraph polynomial time algorithms algorithmic complexity color acyclic hypergraphs Boolean switching hypergraph saturation problem self-complemented hypergraphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65)

Cited In (only showing first 100 items - show all)

Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
An approximation algorithm for submodular hitting set problem with linear penalties
On the complexity of monotone dualization and generating minimal hypergraph transversals
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Lower bounds for three algorithms for transversal hypergraph generation
The adjacency matrix of a graph as a data table: a geometric perspective
Enumeration of Minimal Dominating Sets and Variants
Dual-bounded generating problems: Weighted transversals of a hypergraph
Generating all maximal models of a Boolean expression
Bidual Horn functions and extensions
Approximate inference of functional dependencies from relations
On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
NP-completeness: A retrospective
A study on monotone self-dual Boolean functions
On Maximal Chain Subgraphs and Covers of Bipartite Graphs
On enumerating minimal dicuts and strongly connected subgraphs
The parameterized complexity of maximality and minimality problems
A global parallel algorithm for the hypergraph transversal problem
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
Generating all vertices of a polyhedron is hard
An average study of hypergraphs and their minimal transversals
A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
Self-duality of bounded monotone Boolean functions and related problems
SYMMETRY GEOMETRY BY PAIRINGS
Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
A framework for incremental generation of closed itemsets
Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
Enumerating minimal dominating sets in chordal bipartite graphs
Extended dualization: application to maximal pattern mining
Sequential testing of complex systems: a review
On the counting complexity of propositional circumscription
Horn axiomatizations for sequential data
On Tackling Explanation Redundancy in Decision Trees
Maximal sensitivity of Boolean nested canalizing functions
Enumerating maximal consistent closed sets in closure systems
Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
On a cone covering problem
Decompositions of positive self-dual Boolean functions
Minimum self-dual decompositions of positive dual-minor Boolean functions
Generating cut conjunctions in graphs and related problems
Resolution based algorithms for the transversal hypergraph generation problem
Generating dual-bounded hypergraphs
Minimal dominating sets in interval graphs and trees
Computational aspects of monotone dualization: a brief survey
On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
Logical Foundations of Possibilistic Keys
Counting minimal transversals of \(\beta\)-acyclic hypergraphs
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
Counting and enumerating preferred database repairs
Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
Well-totally-dominated graphs
Pareto-optimal patterns in logical analysis of data
Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
Combining probabilistic logic programming with the power of maximum entropy
Complexity of DNF minimization and isomorphism testing for monotone formulas
Algorithms for \(k\)-meet-semidistributive lattices
Discovery of the \(D\)-basis in binary tables based on hypergraph dualization
Parameterized ceteris paribus preferences over atomic conjunctions under conservative semantics
Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
On the complexity of enumerating pseudo-intents
Simple graphs in granular computing
Version spaces and the consistency problem
Minimum implicational basis for \(\wedge\)-semidistributive lattices
Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
Bounds on upper transversals in hypergraphs
Recognition and dualization of disguised bidual Horn functions.
The Minimal Hitting Set Generation Problem: Algorithms and Computation
Mining ℰℒ⊥ Bases with Adaptable Role Depth
Possibilistic keys
Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
Dualization in lattices given by implicational bases
Prediction-hardness of acyclic conjunctive queries
Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints
Interior and exterior functions of positive Boolean functions.
The complexity of dependency detection and discovery in relational databases
On the complexity of inducing categorical and quantitative association rules
Minimal Roman dominating functions: extensions and enumeration
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
Tree-shellability of Boolean functions
A fast compound algorithm for mining generators, closed itemsets, and computing links between equivalence classes
Translation among CNFs, characteristic models and ordered binary decision diagrams
Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
Enumeration and maximum number of maximal irredundant sets for chordal graphs
On the dualization in distributive lattices and related problems
Enumerating Minimal Transversals of Hypergraphs without Small Holes
Generating minimal redundant and maximal irredundant subhypergraphs
On the fractional chromatic number of monotone self-dual Boolean functions
Translating between the representations of a ranked convex geometry
Pairings and related symmetry notions
Granular computing on basic digraphs
Affine planes and transversals in 3-uniform linear hypergraphs
On the fixed-parameter tractability of the equivalence test of monotone normal forms
Combinatorial optimization in system configuration design
Dependency structures for decision tables

This page was built for publication: Identifying the Minimal Transversals of a Hypergraph and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862797)