Counting Minimal Transversals of β-Acyclic Hypergraphs

Abstract : We prove that one can count in polynomial time the number of minimal transversals of β-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. Kanté and T. Uno, Counting Minimal Dominating Sets, TAMC'17].
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01923090
Contributor : Florent Capelli <>
Submitted on : Wednesday, November 14, 2018 - 10:28:44 PM
Last modification on : Thursday, June 27, 2019 - 1:55:13 PM

Links full text

Identifiers

Citation

Benjamin Bergougnoux, Florent Capelli, Mamadou Moustapha Kanté. Counting Minimal Transversals of β-Acyclic Hypergraphs. Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.10.002⟩. ⟨hal-01923090⟩

Share

Metrics

Record views

83