An average study of hypergraphs and their minimal transversals

DOI10.1016/j.tcs.2015.06.052zbMath1328.68087OpenAlexW857871428MaRDI QIDQ2355712

Julien David, François Rioult, Arnaud Mary, Loïck Lhote

Publication date: 24 July 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.052

zbMATH Keywords

hypergraphenumerationprobabilistic analysisaverage complexitygeneric complexityminimal transversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Loose Hamilton cycles in random uniform hypergraphs
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Computational aspects of monotone dualization: a brief survey
• Generic-case complexity, decision problems in group theory, and random walks.
• Almost all monotone Boolean functions are polynomially learnable using membership queries
• Phase transition of random non-uniform hypergraphs
• Efficient algorithms for dualizing large-scale hypergraphs
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Generic complexity of undecidable problems
• Creation and Growth of Components in a Random Hypergraph Process
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the 2-colorability of random hypergraphs
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• A new approach to the orientation of random hypergraphs