Identifying the Minimal Transversals of a Hypergraph and Related Problems

DOI10.1137/S0097539793250299zbMath0842.05070MaRDI QIDQ4862797

Publication date: 28 July 1996

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

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

Mathematics Subject Classification ID

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

Related Items

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