Efficient algorithms for dualizing large-scale hypergraphs

DOI10.1016/j.dam.2014.01.012zbMath1288.05188OpenAlexW2788537315MaRDI QIDQ2449091

Takeaki Uno, Keisuke Murakami

Publication date: 6 May 2014

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

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

zbMATH Keywords

enumerationdualizationhypergraph transversalreal-world dataminimal set coveringminimal hitting setexperimental efficiency

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (18)

Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Optimal resource allocation enables mathematical exploration of microbial metabolic configurations ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Compression with wildcards: all exact or all minimal hitting sets ⋮ One approach to decoding monotone logical function ⋮ Embedding Dimension of a Good Semigroup ⋮ Enumerating models of DNF faster: breaking the dependency on the formula size ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Discovery of the \(D\)-basis in binary tables based on hypergraph dualization ⋮ RQL: a query language for rule discovery in databases ⋮ Dualization of Boolean functions using ternary decision diagrams ⋮ On the logical analysis of partially ordered data in the supervised classification problem ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Measuring the Implications of the D-Basis in Analysis of Data in Biomedical Studies ⋮ Implementing Efficient All Solutions SAT Solvers ⋮ Asymptotically optimal dualization algorithms ⋮ An average study of hypergraphs and their minimal transversals

Uses Software

• UCI-ml

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Computational aspects of monotone dualization: a brief survey
• Lower bounds for three algorithms for transversal hypergraph generation
• On maximal frequent and minimal infrequent sets in binary matrices
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Reverse search for enumeration
• An Efficient Algorithm for the Transversal Hypergraph Generation
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating dual-bounded hypergraphs
• Galois Connexions
• Algorithms - ESA 2003

This page was built for publication: Efficient algorithms for dualizing large-scale hypergraphs