Counting minimal transversals of \(\beta\)-acyclic hypergraphs

DOI10.1016/j.jcss.2018.10.002zbMath1414.05022arXiv1808.05017OpenAlexW2887600670MaRDI QIDQ1713476

Florent Capelli, Mamadou Moustapha Kanté, Benjamin Bergougnoux

Publication date: 25 January 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.05017

zbMATH Keywords

counting problemdominating setsstrongly chordal graphsminimal transversals\(\beta\)-acyclic hypergraphs

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Hypergraphs (05C65) Transversal (matching) theory (05D15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Bounding the Mim-Width of Hereditary Graph Classes.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximately counting locally-optimal structures
• The complexity of computing the permanent
• Computational aspects of monotone dualization: a brief survey
• On the counting complexity of propositional circumscription
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• Counting Minimal Dominating Sets
• Three Partition Refinement Algorithms
• Graph Classes: A Survey
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the Enumeration of Minimal Dominating Sets and Related Notions
• The monadic second-order logic of graphs XVI : Canonical graph decompositions