Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
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.
|
Submitted: March 2003. Revised: August 2005. Communicated by Alan Gibbons |
Journal of Graph Algorithms and Applications |