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

Abstract:

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.

Key words: cluster vertex deletion, clique, NP-complete, approximation algorithm, cluster analysis