Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
复制标题
派系覆盖的数据缩减、精确和启发式算法
DOI：
10.1137/1.9781611972863.9
复制
发表时间：
2006
影响因子：
0.5
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
J. Gramm;Jiong Guo;Falk Hüffner;R. Niedermeier
用最小数量的团覆盖图的边是一个具有许多应用的np完全问题。最先进的求解算法是20世纪70年代的多项式时间启发式算法。我们提出了对这种启发式的改进。然而，我们的主要贡献是开发了高效和有效的多项式时间数据约简规则，结合搜索树算法，允许在竞争时间内精确地解决问题。这被真实世界和合成数据的实验所证实。此外，我们还证明了团覆盖边的定参数可跟踪性。
To cover the edges of a graph with a minimum number of cliques is an NP-complete problem with many applications. The state-of-the-art solving algorithm is a polynomial-time heuristic from the 1970's. We present an improvement of this heuristic. Our main contribution, however, is the development of efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.