Generating dual-bounded hypergraphs

DOI10.1080/1055678021000060801zbMath1065.05066OpenAlexW2008110002WikidataQ59560633 ScholiaQ59560633MaRDI QIDQ4405941

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

Publication date: 2002

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/1055678021000060801

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ Computational aspects of monotone dualization: a brief survey ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Discovery of the \(D\)-basis in binary tables based on hypergraph dualization ⋮ Measuring the Implications of the D-Basis in Analysis of Data in Biomedical Studies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Design by example: An application of Armstrong relations
• 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
• On generating all maximal independent sets
• On frequent sets of Boolean matrices
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• An ordering (enumerative) algorithm for nonlinear \(0-1\) programming
• On the frequency of the most frequently occurring variable in dual monotone DNFs
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Interior and exterior functions of Boolean functions
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• 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
• New results on monotone dualization and generating hypergraph transversals
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Rado's theorem for polymatroids
• The solvability of positional games in pure strategies
• A New Algorithm for Generating All the Maximal Independent Sets
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Predicting Cause-Effect Relationships from Incomplete Discrete Observations
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions
• A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions

This page was built for publication: Generating dual-bounded hypergraphs