We study the maximum edge-weighted clique problem, a problem related to the maximum (vertexweighted) 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.

(2019). A new branch-and-bound algorithm for the maximum edge-weighted clique problem [journal article - articolo]. In EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. Retrieved from http://hdl.handle.net/10446/229306

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

Coniglio, Stefano;
2019

Abstract

We study the maximum edge-weighted clique problem, a problem related to the maximum (vertexweighted) 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.
articolo
San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana
(2019). A new branch-and-bound algorithm for the maximum edge-weighted clique problem [journal article - articolo]. In EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. Retrieved from http://hdl.handle.net/10446/229306
File allegato/i alla scheda:
File Dimensione del file Formato  
2019-EJOR.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 965.86 kB
Formato Adobe PDF
965.86 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229306
Citazioni
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 12
social impact