Generating minimal redundant and maximal irredundant subhypergraphs

DOI10.1016/j.dam.2024.07.006zbMATH Open1548.05247MaRDI QIDQ6611070

Kazuhisa Makino, Endre Boros

Publication date: 26 September 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph dominationsequential generationredundant/irredundant hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Cites Work

• Computational aspects of monotone dualization: a brief survey
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• On generating all maximal independent sets
• On frequent sets of Boolean matrices
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• A complexity theory for hard enumeration problems
• Complexity of identification and dualization of positive Boolean functions
• Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating dual-bounded hypergraphs
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the Enumeration of Minimal Dominating Sets and Related Notions
• Covering Problems: Duality Relations and a New Method of Solution

This page was built for publication: Generating minimal redundant and maximal irredundant subhypergraphs