Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00107
An Efficient Algorithm for the Transversal Hypergraph Generation
Dimitris J. Kavvadias and
Elias C. Stavropoulos
Vol. 9, no. 2, pp. 239-264, 2005. Regular paper.
Abstract 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.
|
Journal Supporters
|