Dual-bounded generating problems: Weighted transversals of a hypergraph

DOI10.1016/j.dam.2002.12.004zbMath1062.68083OpenAlexW2009689335MaRDI QIDQ1878396

Endre Boros, Kazuhisa Makino, Vladimir A. Gurvich, Leonid G. Khachiyan

Publication date: 19 August 2004

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

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

zbMATH Keywords

Data miningBoolean programmingpolynomial timeIncrementalDualizationDual hypergraphIntersection inequalitiesMaximal frequent setMinimal infrequent setMultiple transversalPartial transversalThreshold Boolean function

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Boolean programming (90C09)

Related Items (7)

On Dualization over Distributive Lattices ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Stability of two player game structures ⋮ Generating dual-bounded hypergraphs

Cites Work

• 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
• On the frequency of the most frequently occurring variable in dual monotone DNFs
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Interior and exterior functions of Boolean functions
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Minimum self-dual decompositions of positive dual-minor Boolean functions
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Stable effectivity functions and perfect graphs
• 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
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• A New Algorithm for Generating All the Maximal Independent Sets
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• 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: Dual-bounded generating problems: Weighted transversals of a hypergraph