Lower bounds for three algorithms for transversal hypergraph generation
From MaRDI portal
Publication:1028117
DOI10.1016/j.dam.2008.10.004zbMath1177.05116OpenAlexW1989328905MaRDI QIDQ1028117
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.10.004
Related Items
Indiscernibility structures induced from function sets : Graph and digraph case ⋮ The adjacency matrix of a graph as a data table: a geometric perspective ⋮ Simplicial complexes and closure systems induced by indistinguishability relations ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Decision systems in rough set theory: A set operatorial perspective ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Transformation and decomposition of clutters into matroids ⋮ Local dissymmetry on graphs and related algebraic structures ⋮ Granular computing on basic digraphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- On generating all maximal independent sets
- On the complexity of inferring functional dependencies
- On the frequency of the most frequently occurring variable in dual monotone DNFs
- Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
- On enumerating minimal dicuts and strongly connected subgraphs
- An Efficient Algorithm for the Transversal Hypergraph Generation
- On Berge Multiplication for Monotone Boolean Dualization
- A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Using Transversals for Discovering XML Functional Dependencies
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
