团图点删除问题的近似算法  

Approximation algorithm of cluster vertex deletion

作　　者：高文宇[1] 李华[1] 

机构地区：[1]广东财经大学信息学院,广州510320

出　　处：《计算机应用》2015年第8期2137-2139,2146,共4页journal of Computer Applications

基　　金：广东省自然科学基金资助项目(8151032001000013);广东省教育厅科技创新项目(2013KJCX0084)

摘　　要：针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。Since the solution set obtained by 3-approximation algorithm of cluster vertex deletion problem is probably big, a new approximation algorithm was proposed through analyzing the characteristics of cluster. In the new algorithm, the number of P3 related to each vertex in the graph was counted by examining first-order neighbors and second-order neighbors of each vertex, and then the vertex with maximum number of P3 was selected into the solution set to eliminate P3 as soon as possible, which led to a smaller vertex deletion set. In order to verify the performance of this new algorithm, several sets of randomized simulation were designed. The simulation results show that the new algorithm outperforms the classic 3-approximation algorithm.

关 键 词：团图点删除 团 NP完全 近似算法 团图分析 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]