On the average-case complexity of Berge algorithm

DOI10.1016/J.TCS.2025.115702MaRDI QIDQ6875310zbMATH OpenFDO

Authors Julien David, M. Gholami, Loïck Lhote

Publication date 14 January 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115702

zbMATH Keywords

hypergraphsanalytic combinatoricsaverage-case complexityminimal transversalBerge algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1961543 (Why is no real title available?)
• scientific article; zbMATH DE number 2038737 (Why is no real title available?)
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Generalisation of Stirling's Formula.
• A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
• A data mining formalization to improve hypergraph minimal transversal computation
• Advances in Artificial Intelligence
• An Efficient Algorithm for the Transversal Hypergraph Generation
• An average study of hypergraphs and their minimal transversals
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Analytic combinatorics
• Automata, languages and programming. 24th international colloquium, ICALP '97, Bologna, Italy, July 7--11, 1997. Proceedings
• Efficient algorithms for dualizing large-scale hypergraphs
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
• Graph Classes: A Survey
• How to assign votes in a distributed system
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• LATIN 2004: Theoretical Informatics
• Lower bounds for three algorithms for transversal hypergraph generation
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• New results on monotone dualization and generating hypergraph transversals
• On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles.
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of inferring functional dependencies
• On the enumeration of minimal dominating sets and related notions
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Random graphs.
• The depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• The shortest-path problem for graphs with random arc-lengths
• Transversal hypergraphs and families of polyhedral cones

This page was built for publication: On the average-case complexity of Berge algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875310)