计算机应用
計算機應用
계산궤응용
Journal of Computer Applications
2015年
8期
2137-2139,2146
,共4页
团图点删徐%团%NP完全%近似算法%团图分析
糰圖點刪徐%糰%NP完全%近似算法%糰圖分析
단도점산서%단%NP완전%근사산법%단도분석
cluster vertex deletion%clique%NP-complete%approximation algorithm%cluster analysis
针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法.新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集.为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较.随机实验表明,新算法较经典的3-近似算法有明显的优势.
針對糰圖點刪除問題的3-近似算法得到的近似解可能較大的問題,通過對糰圖點刪除問題及糰圖特性的分析,提齣瞭該問題的一箇新的近似算法.新算法通過攷察圖中節點的一階和二階鄰點來計算節點關聯的P3的數目,然後優先選擇P3數最大的節點加入解集,以期儘快消除圖中的P3,從而最終穫得較小的點刪除集.為檢驗算法效果,設計瞭多組不同場景的隨機實驗對新算法和經典的3-近似算法進行瞭比較.隨機實驗錶明,新算法較經典的3-近似算法有明顯的優勢.
침대단도점산제문제적3-근사산법득도적근사해가능교대적문제,통과대단도점산제문제급단도특성적분석,제출료해문제적일개신적근사산법.신산법통과고찰도중절점적일계화이계린점래계산절점관련적P3적수목,연후우선선택P3수최대적절점가입해집,이기진쾌소제도중적P3,종이최종획득교소적점산제집.위검험산법효과,설계료다조불동장경적수궤실험대신산법화경전적3-근사산법진행료비교.수궤실험표명,신산법교경전적3-근사산법유명현적우세.
