Research of Fixed Parameter Algorithm for Clique Partition Problem

Research of Fixed Parameter Algorithm for Clique Partition Problem
复制标题

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

DOI：
--
复制
发表时间：
2011
期刊：
Computer Engineering
影响因子：
--
通讯作者：
Rudolf FLEISCHER
Rudolf FLEISCHER
中科院分区：
其他
文献类型：
--
作者：
Wu, Xiaotian;Lin, Yuhao;Rudolf FLEISCHER

文献摘要

相似文献

图论中的团划分（CP）问题是NP完全问题，很难在多项式时间内求解，本文研究了CP问题的固定参数算法，提出了一种新的无K4图的约简规则，并结合深度界搜索树的方法，它提高了K4-K5中团划分的固定参数可处理（FPT）算法的运行时间。实验结果表明，在稀疏图的情况下，改进算法的效率比原算法提高了至少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.