在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d).给出一种求解低度图的最大团的确定性算法.该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题.算法时间复杂度为O(d·n~3).其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m.
In the Maximum Clique Problem(MCP),setting m as a threshold means that it is easy to compute MCP of a graph whose vertices are not greater than m,and the time complexity is O(d).An exact algorithm to compute MCP in low-degree graphs is presented.The algorithm solves MCP suecessfully by dividing the vertices of the graph gradually and computing MCP separately.The algorithm is easy to be realized,and the time complexity is O(d·n~3).n represents graph vertices,the maximum degree of vertex in graph is degree lower than m by gradually deleting the vertices which are lower than m.