An average study of hypergraphs and their minimal transversals

DOI10.1016/J.TCS.2015.06.052MaRDI QIDQ2355712zbMATH OpenOpenAlexFDO

Authors Julien David, Arnaud Mary, François Rioult, 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

average complexityenumerationgeneric complexityhypergraphminimal transversalprobabilistic analysis

Mathematics Subject Classification ID

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

Recommendations

• Computing and Combinatorics
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• A global parallel algorithm for the hypergraph transversal problem
• Faster Algorithms to Enumerate Hypergraph Transversals

Cites work

• A data mining formalization to improve hypergraph minimal transversal computation
• A new approach to the orientation of random hypergraphs
• Almost all monotone Boolean functions are polynomially learnable using membership queries
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Analytic combinatorics
• Computational aspects of monotone dualization: a brief survey
• Creation and Growth of Components in a Random Hypergraph Process
• Efficient algorithms for dualizing large-scale hypergraphs
• Generic complexity of undecidable problems
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Loose Hamilton cycles in random uniform hypergraphs
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On the 2-colorability of random hypergraphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction

Cited in

(4)

• An averaging process on hypergraphs
• On the average-case complexity of Berge algorithm
• Random generation of source vectors with a fixed preponderant property
• On \(K_{s,t}\)-minors in graphs with given average degree

This page was built for publication: An average study of hypergraphs and their minimal transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355712)