团图点删除问题的近似算法
来源：计算机应用杂志2015年第8期北京时间：
作者：高文宇, 李华
单位：广东财经大学 信息学院, 广州 510320
摘要：针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。
关键词：团图点删除,团,NP完全,近似算法,团图分析
基金资助：广东省自然科学基金资助项目(8151032001000013);广东省教育厅科技创新项目(2013KJCX0084)。
