Find in Library
Search millions of books, articles, and more
Indexed Open Access Databases
NK-MaxClique and MMCQ: Tow New Exact Branch and Bound Algorithms for the Maximum Clique Problem
oleh: Neda Mohammadi, Mehdi Kadivar
Format: | Article |
---|---|
Diterbitkan: | IEEE 2020-01-01 |
Deskripsi
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.