Counting Minimal Transversals of β-Acyclic Hypergraphs

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].

Mots clés

Counting problem Minimal transversals Dominating sets β-Acyclic Hypergraphs Strongly chordal graphs

Domaines

Algorithme et structure de données [cs.DS]

Florent Capelli : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01923090

Soumis le : mercredi 14 novembre 2018-22:28:44

Dernière modification le : mercredi 24 janvier 2024-09:54:23

Dates et versions

hal-01923090 , version 1 (14-11-2018)

Identifiants

HAL Id : hal-01923090 , version 1
ARXIV : 1808.05017
DOI : 10.1016/j.jcss.2018.10.002

Citer

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

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

PRES_CLERMONT CNRS INRIA LIMOS CRISTAL INRIA2 CRISTAL-LINKS UNIV-LILLE CLERMONT-AUVERGNE-INP

79 Consultations

0 Téléchargements