团分划问题的固定参数算法研究

Research of Fixed Parameter Algorithm for Clique Partition Problem

图论中的团分划问题属于NP-完全问题,难以在多项式时间内解决。为此,对团分划问题的固定参数算法进行研究,提出一个针对K4-free图的新归约法则,结合深度限制搜索树技术对K4-free图中的团分划固定参数可解类算法做出改进。实验结果表明,与原算法相比,在稀疏图的情况下改进算法效率提高了30%。

Clique Partition（CP） problem in graph theory is NP-complete,so it＇s difficult to solve it in polynomial time.This paper studies fixed parameter algorithm for CP and proposes a new reduction rule for K4-free graphs.Combing with the way of depth-bound search tree,it improves the running time of Fixed Parameter Tractable（FPT） algorithm for Clique partition in K4-free graph.Experimental results show that the efficiency of the improved algorithm is higher than the original at least thirty percent in the case of sparse graph.