NK-MaxClique and MMCQ: Tow new exact branch and bound algorithms for the maximum clique problem
2020
The maximum clique problem (MCP) is a fundamental problem in combinatorial optimization which finds important applications in real-word. This paper describes two new efficient branch-and-bound maximum clique algorithms NK-MaxClique and MMCQ, designed for solving MCP. We define some pruning conditions based on core numbers and vertex ordering to efficiently remove many of the search space. With respect to this ordering, the algorithms consider the vertices respectively to find the corresponding maximum clique in subproblems. Simulation results demonstrate that the algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
34
References
0
Citations
NaN
KQI