English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/197324
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 upper bound for the maximum weight clique problem

AuthorsLi, Chu Min; Liu, Yanli; Jiang, Hua; Manyà, Felip CSIC ORCID ; Li, Yu
KeywordsCombinatorial optimization
Branch and bound
Maximum weight clique problem
Upper bound
Weight cover
Issue Date1-Oct-2018
CitationEuropean Journal of Operational Research 270(1): 66-77 (2018)
AbstractThe maximum weight clique problem (MWCP) for a vertex-weighted graph is to find a complete subgraph in which the sum of vertex weights is maximum. The main goal of this paper is to develop an efficient branch-and-bound algorithm to solve the MWCP. As a crucial aspect of branch-and-bound MWCP algorithms is the incorporation of a tight upper bound, we first define a new upper bound for the MWCP, called UBWC, that is based on a novel notion called weight cover. The idea of a weight cover is to compute a set of independent sets of the graph and define a weight function for each independent set so that the weight of each vertex of the graph is covered by such weight functions. We then propose a new branch-and-bound MWCP algorithm called WC-MWC that uses UBWC to reduce the number of branches of the search space that must be traversed by incrementally constructing a weight cover for the graph. Finally, we present experimental results that show that UBWC reduces the search space much more than previous upper bounds, and the new algorithm WC-MWC outperforms some of the best performing exact and heuristic MWCP algorithms on both small/medium graphs and real-world massive graphs.
Publisher version (URL)http://dx.doi.org/10.1016/j.ejor.2018.03.020
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,35 kBAdobe PDFThumbnail
Show full item record
Review this work

Related articles:

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