本文選題：NP難度 + 大規(guī)模圖��； 參考：《華中科技大學(xué)學(xué)報(自然科學(xué)版)》2017年12期

【摘要】：將最大團求解算法融入到極大團枚舉算法中,提出了兩種帶極大團下限的極大團枚舉算法及多種預(yù)處理篩選策略,通過迭代將不可能包含在極大團中的部分點與邊刪除,使得搜索空間大幅減小.在搜索策略上,將求解最大團問題的貪心染色算法、增量MaxSAT推理算法與極大團枚舉算法相融合,并結(jié)合最佳篩選策略,提出了染色-關(guān)鍵點融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚舉算法BKFS(Bron-Kerbosch with filtering and MaxSAT).結(jié)果表明:在多個大型算例上,BKFC算法平均時間僅為加入預(yù)處理的改進經(jīng)典算法的68.8%;由于經(jīng)典算法無法在大型算例上運行,在小數(shù)據(jù)測試中,BKFC算法平均時間僅為沒有預(yù)處理策略的經(jīng)典算法的2.2%.
[Abstract]:The maximum cluster solving algorithm is integrated into the maximum cluster enumeration algorithm. Two maximum cluster enumeration algorithms with maximum clique lower bound and various preprocessing and filtering strategies are proposed. By iteration, some points and edges that can not be included in the maximal cluster are deleted. Makes the search space greatly reduced. In search strategy, greedy coloring algorithm, incremental MaxSAT reasoning algorithm and maximal cluster enumeration algorithm are combined with the best selection strategy. A color-key point fusion algorithm, BKFC(Bron-Kerbosch with filtering and coloring, and an enumeration algorithm based on incremental MaxSAT reasoning, BKFS(Bron-Kerbosch with filtering and MaxSAT, are proposed. The results show that the average time of BKFC algorithm is only 68.8% of that of the improved classical algorithm with preprocessing on many large examples, because the classical algorithm can not run on large scale examples. In the small data test, the average time of BKFC algorithm is only 2.2 of that of the classical algorithm without preprocessing strategy.
【作者單位】： 華中科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院;深圳華中科技大學(xué)研究院;
【基金】：國家自然科學(xué)基金資助項目(61772219,61472147,61602196) 深圳市科技計劃資助項目(JCYJ20170307154749425)
【分類號】：O157.5;TP301.6

【相似文獻】

相關(guān)期刊論文 前2條

1 陳偉侯,張錄達(dá),朱正元;一個四元組合問題的研究[J];中央民族大學(xué)學(xué)報(自然科學(xué)版);2005年03期

2 沈厚才，仲偉俊，徐南榮;一類基于優(yōu)先級的隱枚舉兩層決策方法[J];東南大學(xué)學(xué)報;1996年01期

，

本文編號：1788238