Result: On the average complexity of Berge Algorithm ; Sur la complexité moyenne de l'algorithme de Berge
Title:
On the average complexity of Berge Algorithm ; Sur la complexité moyenne de l'algorithme de Berge
Authors:
Contributors:
Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Equipe AMACC - Laboratoire GREYC - UMR6072, Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU), École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN)
Source:
https://hal.science/hal-04637413 ; 2025.
Publisher Information:
CCSD
Publication Year:
2025
Collection:
Normandie Université: HAL
Subject Terms:
Document Type:
Report
report
Language:
English
Availability:
Rights:
http://creativecommons.org/licenses/by/ ; info:eu-repo/semantics/OpenAccess
Accession Number:
edsbas.9E4EE4F3
Database:
BASE
Further Information
Given a hypergraph, computing its transversal hypergraph is a classical problem whose exactworst-case complexity is still unknown today. In this article, for random hypergraph models à laErdos and Renyi, we compute the average number of minimal transversals. We also study theaverage complexity of Berge’s algorithm, which sequentially enumerates the minimal transversals.We prove that the average complexity of Berge is quasi-linear in the average number of minimaltraverses. Our contribution is also methodological: we use a wide range of analytic combinatoricstechniques to extract the coefficients of probabilistic generating functions.