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

关键词: 图论, 团分划, 固定参数算法, 规约法则, 深度限制搜索树

Abstract: 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.

Key words: graph theory, Clique Partition(CP), fixed parameter algorithm, reduction rule, depth-bound search tree

中图分类号: 

• TP311