Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 307, Issue 3, Pages 1008-1025Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2022.10.028
Keywords
Combinatorial optimization; Exact algorithm; Branch -and -bound algorithm; Maximum clique problem
Ask authors/readers for more resources
Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications.
Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications. The newly developed ex-act approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The first one is based on graph colouring procedures and partial maximum satisfiability problems arising in the branching scheme. The second one is a filtering phase based on constraint programming and domain propagation techniques. CliSAT is designed for structured MCP instances which are computationally difficult to solve since they are dense and contain many interconnected large cliques. Extensive experi-ments on hard benchmark instances, as well as new hard instances arising from different applications, show that CliSAT outperforms the state-of-the-art MCP algorithms, in some cases by several orders of magnitude.(c) 2022 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available