Questions About The Largest Group Of Branch Search Algorithm Optimization

The maximum clique problem(MCP)is a classic combinatorial optimizationproblem in the graph theory, the description is simple but difficult to solve, and it is aNP complete problems. The problem had a very close relationship with classicproblems in the graph theory, it can be converted mutually in polynomial time, such ascoloration problems, the minimum vertex covering problem, the maximum independentset problem in undirected graph, knapsack problem and salesperson problem.Theresearch on MCP has important significance to solve the problems in the graph theory.As a classic combinatorial optimization problem, MCP has been widely used inpeople’s life, such as personnel activity arrangements, market analysis method, theselection of fault diagnosis, machine signal transmission and many other applicationdomain.So the research has high value of application.The algorithm included deterministic techniques and non-deterministic techniques.The deterministic techniques is required the optimal solution within the limited time,while the non-deterministic can’t guarantee the optimal solution. MCP is a NP problemwhich may not get the optimal solution when the undirected graph is large in scale.Non-deterministic techniques can get similarly most optimal solution within limitedtime for the undirected graph.The thesis introduced the application background of MCP firstly. Then introducedthe results of the study on MCP in undirected graph, and gave the popular methods on it.Then analyzed and studied the deterministic techniques for MCP which also be a branchand bound algorithm. The key of the branch and bound algorithm to solve MCP is thepartition of undirected graph and the estimation of the upper bound and lower boundfor the induced subgraph.The purpose of the branch selection strategy in undirectedgraph is divide the big scale graph into small one to maximize reduce the scale. Theestimation for divide subgraph can improve branch pruning efficiency, reduce thesearched space when searching max clique in undirected graph so as to improve theefficiency of searching. the thesis analyzed the undirected graph carefully, based onthe structure character of the undirected graph and the skills for MaxSAT problem to optimize the estimation of upper bound in subgraph,thus optimize branch and boundalgorithm for MCP. The thesis tested the optimized branch and bound algorithm forcontrast, the result showed that the efficiency of the algorithm had been improvedgreatly.