计算机应用 ›› 2015, Vol. 35 ›› Issue (8): 2137-2139.DOI: 10.11772/j.issn.1001-9081.2015.08.2137

• 先进计算 • 上一篇    下一篇

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

高文宇, 李华   

  1. 广东财经大学 信息学院, 广州 510320
  • 收稿日期:2015-03-10 修回日期:2015-05-18 出版日期:2015-08-10 发布日期:2015-08-14
  • 通讯作者: 高文宇(1972-),男,湖南永州人,教授,博士,CCF会员,主要研究方向:算法理论及应用、网络优化,gwy@gdufe.edu.cn
  • 作者简介:李华(1972-),女,湖南永州人,实验师,主要研究方向:计算机网络。
  • 基金资助:

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

Approximation algorithm of cluster vertex deletion

GAO Wenyu, LI Hua   

  1. School of Information Science, Guangdong University of Finance and Economics, Guangzhou Guangdong 510320, China
  • Received:2015-03-10 Revised:2015-05-18 Online:2015-08-10 Published:2015-08-14

摘要:

针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。

关键词: 团图点删除, 团, 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

中图分类号: