Retour aux résultats
Articles (2019), European Journal of Operational Research, 278 (1), pp. 76-90

A new branch-and-bound algorithm for the maximum edge-weighted clique problem

SAN SEGUNDO Pablo, CONIGLIO Stefano, FURINI Fabio, LJUBIC Ivana

We study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances. Lien vers l'article

SAN SEGUNDO, P., CONIGLIO, S., FURINI, F. and LJUBIC, I. (2019). A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 278(1), pp. 76-90.

Mots clés : #Combinatorial-optimization,-Branch, #and, #bound,-Maximum-edge, #weighted-clique-problem