Solution Algorithm for Maximum Clique in Low-degree Graphs
Fan Tie-sheng · Jisuanji gongcheng · 2010
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 successfully 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·n3). n represents graph vertices, the maximum degree of vertex in graph is lower than m, or the graph can make all the vertex degree lower than m by gradually deleting the vertices which are lower than m.