New Results on Monotone Dualization and Generating Hypergraph Transversals

DOI10.1137/S009753970240639XzbMath1052.68101OpenAlexW2087134747WikidataQ59259700 ScholiaQ59259700MaRDI QIDQ4706216

Thomas Eiter, Kazuhisa Makino, Georg Gottlob

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970240639x

zbMATH Keywords

combinatorial enumeration treewidth hypergraphs dualization limited nondeterminism hypergraph acyclicity transversal computation output-polynomial algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Database theory (68P15) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30) Graph algorithms (graph-theoretic aspects) (05C85) Boolean functions (06E30)

Related Items

Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data ⋮ Blocker size via matching minors ⋮ Extended dualization: application to maximal pattern mining ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ The many benefits of putting stack filters into disjunctive or conjunctive normal form ⋮ Minimal dominating sets in interval graphs and trees ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ On the complexity of enumerating pseudo-intents ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Algorithms for \(k\)-meet-semidistributive lattices ⋮ Fast algorithms for implication bases and attribute exploration using proper premises ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Incremental delay enumeration: space and time ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Dualization in lattices given by implicational bases ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Unnamed Item ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).] ⋮ Asymptotically optimal dualization algorithms ⋮ Version spaces and the consistency problem ⋮ An average study of hypergraphs and their minimal transversals