New Results on Monotone Dualization and Generating Hypergraph Transversals
From MaRDI portal
combinatorial enumerationdualizationhypergraph acyclicityhypergraphslimited nondeterminismoutput-polynomial algorithmstransversal computationtreewidth
Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Boolean functions (06E30) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30)
Recommendations
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- scientific article; zbMATH DE number 1670855
- Achieving new upper bounds for the hypergraph duality problem through logic
- Computational aspects of monotone dualization: a brief survey
- Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
Cited in
(55)- On the fractional chromatic number of monotone self-dual Boolean functions
- Lower bounds for three algorithms for transversal hypergraph generation
- Blocker size via matching minors
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- Efficient enumeration of dominating sets for sparse graphs
- On the dualization in distributive lattices and related problems
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- The complexity of dependency detection and discovery in relational databases
- Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
- Fast algorithms for implication bases and attribute exploration using proper premises
- Incremental delay enumeration: space and time
- Resolution based algorithms for the transversal hypergraph generation problem
- Asymptotically optimal dualization algorithms
- An average study of hypergraphs and their minimal transversals
- Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
- On the fixed-parameter tractability of the equivalence test of monotone normal forms
- The many benefits of putting stack filters into disjunctive or conjunctive normal form
- Extended dualization: application to maximal pattern mining
- A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
- The minimal hitting set generation problem: algorithms and computation
- How to apply SAT-solving for the equivalence test of monotone normal forms
- Enumeration of minimal dominating sets and variants
- Minimal dominating sets in interval graphs and trees
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- Achieving new upper bounds for the hypergraph duality problem through logic
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Enumerating minimal transversals of hypergraphs without small holes
- Algorithms for k-meet-semidistributive lattices
- Enumerating Minimal Dominating Sets in Triangle-Free Graphs
- Efficient enumeration of dominating sets for sparse graphs
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- scientific article; zbMATH DE number 7310243 (Why is no real title available?)
- Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
- On the complexity of enumerating pseudo-intents
- Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
- Exactly hittable interval graphs
- Minimal solutions of fuzzy relation equations via maximal independent elements
- New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems
- Enumerating minimal defensive alliances
- Enumeration classes defined by circuits
- Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
- Enumerating minimal solution sets for metric graph problems
- Enumerating minimal solution sets for metric graph problems
- Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
- Hypergraph dualization with \textsf{FPT}-delay parameterized by the degeneracy and dimension
- Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
- Enumeration of minimal hitting sets parameterized by treewidth
- Enumerating minimal dominating sets and variants in chordal bipartite graphs
- From amortized to worst case delay in enumeration algorithms
- Version spaces and the consistency problem
- Enumerating minimal dominating sets in chordal bipartite graphs
- Complexity of DNF minimization and isomorphism testing for monotone formulas
- Computational aspects of monotone dualization: a brief survey
- On the complexity of monotone dualization and generating minimal hypergraph transversals
This page was built for publication: New Results on Monotone Dualization and Generating Hypergraph Transversals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4706216)
