Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

DOI10.1016/j.dam.2007.04.018zbMath1160.68018OpenAlexW1966461202WikidataQ59560588 ScholiaQ59560588MaRDI QIDQ943838

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

Publication date: 10 September 2008

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

Full work available at URL: https://doi.org/10.1016/j.dam.2007.04.018

zbMATH Keywords

dualizationlinear inequalitiesgeneration algorithmshypergraph transversalsmonotone systems of inequalitiespolymatroid inequalitiestransversal inequalities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items

Scientific contributions of Leo Khachiyan (a short overview) ⋮ Lower bounds for three algorithms for transversal hypergraph generation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on finding a maximum empty rectangle
• Dualization of regular Boolean functions
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An O(m n) algorithm for regular set-covering problems
• An inequality for polymatroid functions and its applications.
• Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
• On the generation of circuits and minimal forbidden sets
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Complexity of identification and dualization of positive Boolean functions
• Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Computing Network Reliability in Time Polynomial in the Number of Cuts
• Computing the Largest Empty Rectangle
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Determination of All Minimal Cut-Sets between a Vertex Pair in an Undirected Graph
• Disjunctive Programming
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the Complexity of Some Enumeration Problems for Matroids