Geodesic
An Efficient Algorithm for the Transversal Hypergraph Generation
Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 239-264.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The Transversal Hypergraph Generation is the problem of generating, given a hypergraph, the set of its minimal transversals, i.e., the hypergraph whose hyperedges are the minimal hitting sets of the given one. The purpose of this paper is to present an efficient and practical algorithm for solving this problem. We show that the proposed algorithm operates in a way that rules out regeneration and, thus, its memory requirements are polynomially bounded to the size of the input hypergraph. Although no time bound for the algorithm is given, experimental evaluation and comparison with other approaches have shown that it behaves well in practice and it can successfully handle large problem instances. 
@article{JGAA_2005_9_2_a2,
     author = {Dimitris Kavvadias and Elias Stavropoulos},
     title = {An {Efficient} {Algorithm} for the {Transversal} {Hypergraph} {Generation}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {239--264},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2005},
     doi = {10.7155/jgaa.00107},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00107/}
}
TY  - JOUR
AU  - Dimitris Kavvadias
AU  - Elias Stavropoulos
TI  - An Efficient Algorithm for the Transversal Hypergraph Generation
JO  - Journal of Graph Algorithms and Applications
PY  - 2005
SP  - 239
EP  - 264
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00107/
DO  - 10.7155/jgaa.00107
LA  - en
ID  - JGAA_2005_9_2_a2
ER  - 
%0 Journal Article
%A Dimitris Kavvadias
%A Elias Stavropoulos
%T An Efficient Algorithm for the Transversal Hypergraph Generation
%J Journal of Graph Algorithms and Applications
%D 2005
%P 239-264
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00107/
%R 10.7155/jgaa.00107
%G en
%F JGAA_2005_9_2_a2
Dimitris Kavvadias; Elias Stavropoulos. An Efficient Algorithm for the Transversal Hypergraph Generation. Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 239-264. doi : 10.7155/jgaa.00107. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00107/

Cité par Sources :