English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/216705
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE
Exportar a otros formatos:


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

AuthorsSan Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana
KeywordsCombinatorial optimization
Maximum edge-weighted clique problem
Issue Date1-Oct-2019
PublisherElsevier BV
CitationEuropean Journal of Operational Research 278 (1): 76-90 (2019)
AbstractWe 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.
Publisher version (URL)https://doi.org/10.1016/j.ejor.2019.03.047
Appears in Collections:(CAR) Artículos
Files in This Item:
File Description SizeFormat 
Acceso_Restringido.pdfArtículo restringido15,35 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.