Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
From MaRDI portal
Publication:708383
DOI10.1016/j.disc.2010.05.017zbMath1210.05089OpenAlexW2049703189MaRDI QIDQ708383
Imran Rauf, Khaled M. Elbassioni
Publication date: 11 October 2010
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2010.05.017
Hypergraphs (05C65) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Complexity of identification and dualization of positive Boolean functions
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Treewidth Computation and Extremal Combinatorics
- New results on monotone dualization and generating hypergraph transversals
- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- The Maximum Latency and Identification of Positive Boolean Functions
- 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
- On the Complexity of Some Enumeration Problems for Matroids
- Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
- Advances in Artificial Intelligence
- LATIN 2004: Theoretical Informatics
