最大团问题的竞争决策算法  

Competitive Decision Algorithm for Maximum Clique Problems

作　　者：黄飞[1] 宁爱兵[1] 刘志民[1] 何永梅 张惠珍[1] HUANG Fei;NING Aibing;LIU Zhimin;HE Yongmei;ZHANG Huizhen(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《上海理工大学学报》2018年第6期519-524,共6页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(71401106);上海高校一流学科建设计划(S1201YLXK);高等学校博士学科点专项科研基金联合资助课题(20123120120005)

摘　　要：分析了最大团问题的数学性质,根据推导出来的性质设计求解最大团问题的竞争决策算法,且算法的时间复杂度分析结果为O(n^3)。并用提出的算法求解最大团问题中的标准测试示例,测试结果表明,算法具有良好的求解效果。The mathematical properties of maximum clique problems were analyzed, which can be used to put forward the design of a competitive decision algorithm. The time complexity of the algorithm was analyzed, and the result is O(n^3). To assess the efficiency of the algorithm, it was applied to a set of benchmark problems in maximum clique problems. It turns that our algorithm clearly outperforms other heuristics for solving maximum clique problems, while obtaining better or comparable solutions.

关 键 词：竞争决策算法 最大团 竞争力函数 决策函数 资源交换规则 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]