A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
From MaRDI portal
Publication:1733046
DOI10.1016/j.tcs.2018.09.027zbMath1417.68276OpenAlexW2892384318MaRDI QIDQ1733046
Saurabh Ray, Imran Rauf, Khaled M. Elbassioni
Publication date: 26 March 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.09.027
Hypergraphs (05C65) Enumeration in graph theory (05C30) Parallel algorithms in computer science (68W10)
Related Items
An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Design by example: An application of Armstrong relations
- A global parallel algorithm for the hypergraph transversal problem
- Computational aspects of monotone dualization: a brief survey
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- The complexity of parallel search
- On generating all maximal independent sets
- Efficient partition trees
- Cutting hyperplanes for divide-and-conquer
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Complexity of identification and dualization of positive Boolean functions
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
- Enumerating Spanning and Connected Subsets in Graphs and Matroids
- Advances in Artificial Intelligence
- LATIN 2004: Theoretical Informatics
- Foundations of Information and Knowledge Systems
