@inbook{0442995ba209428da8e62402f914a501,

title = "An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals",

abstract = "Given a finite set V, and a hypergraph H ⊆ 2V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem [9]. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in [9], practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in [9] can be used to give a stronger bound on the running time.",

author = "E. Boros and K. Elbassioni and V. Gurvich and Leonid Khachiyan",

year = "2003",

doi = "10.1007/978-3-540-39658-1_51",

language = "British English",

isbn = "3540200649",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "556--567",

editor = "{di Battista}, Giuseppe and Uri Zwick",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}