CAJ | 학술논문

由于最大团问题(maximum clique problem,MCP)的复杂性、挑战性,以及在数据挖掘等领域的广泛应用,使得求解MCP问题具有非常重要的意义.根据最大团顶点度数较大的特点,提出了从图中第一个度数最大的顶点出发递归求解最大团的算法(简称度数法).为了进一步提高算法的效率,根据图的特点和最大团的特点提出了三个改进的剪枝策略.从理论上证明了算法的正确性和完整性,其时间复杂度为 O(1.442n),空间为 O(n2).通过实验验证了度数法及其改进剪枝策略的效果和效率.
유우최대단문제(maximum clique problem,MCP)적복잡성、도전성,이급재수거알굴등영역적엄범응용,사득구해MCP문제구유비상중요적의의.근거최대단정점도수교대적특점,제출료종도중제일개도수최대적정점출발체귀구해최대단적산법(간칭도수법).위료진일보제고산법적효솔,근거도적특점화최대단적특점제출료삼개개진적전지책략.종이론상증명료산법적정학성화완정성,기시간복잡도위 O(1.442n),공간위 O(n2).통과실험험증료도수법급기개진전지책략적효과화효솔.
The maximum clique problem (MCP) is a significant problem in computer science field because of its complexity, challenging and the extensive applications in data mining and other fields. This paper puts forward a new degree-based approach to finding the maximum clique in a given graph G. According to the characteristic that the degree of the vertexes in a maximum clique is relatively larger, the new approach solves the maximum clique by starting from the first vertex which degree is the largest in the graph G. In order to further improve the efficiency of the algorithm, this paper presents three improvement and pruning strategies based on the characteristics of the graph and the maximum clique. This paper proves that the new approach is correct and complete, the time complexity is O(1.442n) , and the space cost is O(n2) . Finally, an empirical study verifies the effectiveness and efficiency of the new approach.