An Efficient Implementation of a Quasi-polynomial Algorithm for Generating 
Hypergraph Transversals

Boros, Endre; Elbassioni, Khaled M.; Khachiyan, Leonid; Gurvich, Vladimir

doi:10.1007/978-3-540-39658-1_51

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

MPS-Authors

/persons/resource/persons44374

Elbassioni, Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2003). An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals. In Algorithms - ESA 2003 (pp. 556-567). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-EC57-2

Abstract

Given a finite set V, and a hypergraph , the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for . 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.