Counting minimal transversals of β-acyclic hypergraphs1

摘要

We prove that one can count in polynomial time the number of minimal transversals of beta-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in M.M. Kante and T. Uno (2017) [18]. (C) 2018 Elsevier Inc. All rights reserved.