Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 03 décembre 2013 à 14h00 en B107, Uno Takeaki nous parlera de : Efficient Algorithms for Dualizing Large-Scale Hypergraphs

Résumé : A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that J \cap H \ne \emptyset for any J in F The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. In this paper, we introduce a new set system induced by the minimality condition of the hitting sets, that enables us to use efficient pruning methods. We further propose an efficient algorithm for checking the minimality, that enables us to construct time efficient and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in practical time.


Dernière modification : Friday 22 November 2013 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr