In this paper the NP-hard Maximum Clique Problem (MCP) is considered. It is supposed that the input graph is sparse. Also, it is believed that the input graph can have a huge number of vertices. A biphasic algorithm f...
详细信息
ISBN:
(纸本)9783319136714;9783319136707
In this paper the NP-hard Maximum Clique Problem (MCP) is considered. It is supposed that the input graph is sparse. Also, it is believed that the input graph can have a huge number of vertices. A biphasic algorithm for finding the exact solution of the MCP is proposed in the paper. The first phase of the algorithm is the preprocessing of the input graph by decomposing it into atoms. The second phase of the algorithm reduces to an application for each atom classical algorithm Wilf and then to the formation of solutions for the graph as a whole. The level of sparseness of the input graph is given in the form of restrictions on its treewidth. It have been proved that the running time of biphasic algorithm is polynomial in the number of vertices and the exponential of the treewidth of the input graph.
暂无评论