On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs

DOI10.1016/j.tcs.2007.03.005zbMath1125.68088OpenAlexW2025532110MaRDI QIDQ2381526

Endre Boros, Khaled M. Elbassioni, Vladimir A. Gurvich, Leonid G. Khachiyan

Publication date: 18 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.005

zbMATH Keywords

dualizationmaximal independent setpolynomial spacebounded dimensionconformal hypergraphincremental generatingminimal transversalBounded degree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

On the Readability of Monotone Boolean Formulae ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ On the readability of monotone Boolean formulae ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of parallel search
• On generating all maximal independent sets
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Orbits of antichains in ranked posets
• A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
• Orbits of antichains revisited
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• New results on monotone dualization and generating hypergraph transversals
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A New Parallel Algorithm for the Maximal Independent Set Problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
• Constructing a Maximal Independent Set in Parallel
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions

This page was built for publication: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs