Solution of maximum clique problem by using branch and bound method

• Main Authors: Mustafa, Mamat, Mochamad, Suyudi, Ismail, Mohd
• Format: Article
• Language: English
• Published: 2014
• Subjects: QA Mathematics
• Online Access: http://eprints.unisza.edu.my/4934/1/FH02-FIK-14-00728.jpg; http://eprints.unisza.edu.my/4934/
• Institution: Universiti Sultan Zainal Abidin

The maximum clique problems have been widely applied in the field of operations research. The maximum clique problem is finding a solution that is often considered difficult, as well as graph coloring problem, traveling salesman, and so forth. Solution the maximum clique can be done using several methods, such as by using brute force, backtracking, and branch and bound. This paper discusses the branch and bound procedure to solve the maximum clique problem. In the discussion of the method described on the upper and lower bound by implementing a greedy heuristic and branching procedure for determining the maximum clique (G) and minimum coloration (G) in the graph G. Solution the maximum clique problem with this method is beneficial because it provides an alternative perspective on branch and bound, but it is also because they do not need to explain software optimization.