On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
From MaRDI portal
Publication:2381526
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
dualizationmaximal independent setpolynomial spacebounded dimensionconformal hypergraphincremental generatingminimal transversalBounded degree
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
