An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals
An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals
复制标题
生成超图横截面的拟多项式算法的有效实现
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
E. Boros;Khaled M. Elbassioni;V. Gurvich;L. Khachiyan
给定一个有限集V和一个超图(数学{H}子集2^V)，超图横截问题需要枚举(数学{H})的所有极小碰集(横截)。这个问题在实际应用中有着重要的作用，因为许多其他问题都被证明是多项式等价的。Fredman和Khchiyan(1996)给出了一个求解超图横截问题的增量拟多项式时间算法[9]。在本文中，我们给出了该算法的一个有效实现。虽然我们表明我们的实现在运行时间上达到了与[9]中相同的界限，但该实现的实际经验表明它可以显著地更快。我们还表明，对[9]中的算法稍作修改，就可以给出运行时间的更强的界。
Given a finite set V, and a hypergraph (mathcal{H} subseteq 2^V), the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for (mathcal{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.