New results on monotone dualization and generating hypergraph transversals

DOI10.1145/509907.509912zbMath1192.68356OpenAlexW2031661891MaRDI QIDQ3579198

Kazuhisa Makino, Georg Gottlob, Thomas Eiter

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509912

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Pareto-optimal patterns in logical analysis of data ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ On the complexity of enumerating pseudo-intents ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Self-duality of bounded monotone Boolean functions and related problems ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Generating dual-bounded hypergraphs ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits

This page was built for publication: New results on monotone dualization and generating hypergraph transversals