• A new branch-and-bound algorit...

Treffer: A new branch-and-bound algorithm for the Maximum Weighted Clique Problem

Title:
A new branch-and-bound algorithm for the Maximum Weighted Clique Problem
Authors:
Pablo San Segundo, Fabio Furini, Jorge Artieda
Source:
Computers & operations research 110 (2019): 18–33. doi:10.1016/j.cor.2019.05.017
info:cnr-pdr/source/autori:San Segundo, Pablo; Furini, Fabio; Artieda, Jorge/titolo:A new branch-and-bound algorithm for the Maximum Weighted Clique Problem/doi:10.1016%2Fj.cor.2019.05.017/rivista:Computers & operations research/anno:2019/pagina_da:18/pagina_a:33/intervallo_pagine:18–33/volume:110
Publisher Information:
Elsevier BV, 2019.
Publication Year:
2019
Subject Terms:
Branch-and-Bound algorithm, Computational results, Maximum Weighted Clique Problem, 0211 other engineering and technologies, 0202 electrical engineering, electronic engineering, information engineering, 02 engineering and technology
Document Type:
Fachzeitschrift Article
File Description:
application/pdf
Language:
English
ISSN:
0305-0548
DOI:
10.1016/j.cor.2019.05.017
Access URL:
https://www.sciencedirect.com/science/article/pii/S0305054819301303
https://dblp.uni-trier.de/db/journals/cor/cor110.html#SegundoFA19
Rights:
Elsevier TDM
CC BY NC ND
Accession Number:
edsair.doi.dedup.....bd6336fd3b340a63ff71a69e91d4f6f4
Database:
OpenAIRE

Weitere Informationen

We study the Maximum Weighted Clique Problem (MWCP), a generalization of the Maximum Clique Problem in which weights are associated with the vertices of a graph. The MWCP calls for determining a complete subgraph of maximum weight. We design a new combinatorial branch-and-bound algorithm for the MWCP, which relies on an effective bounding procedure. The size of the implicit enumeration tree is largely reduced via a tailored branching scheme, specifically conceived for the MWCP. The new bounding function extends the classical MWCP bounds from the literature to achieve a good trade off between pruning potential and computing effort. We perform extensive tests on random graphs, graphs from the literature and real-world graphs, and we computationally show that our new exact algorithm is competitive with the state-of-the-art algorithms for the MWCP in all these classes of instances. (C) 2019 Elsevier Ltd. All rights reserved.