English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/155298
Share/Impact:
Statistics
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:

Title

On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem

AuthorsLi, Chumin; Jiang, Hua; Manyà, Felip CSIC ORCID
KeywordsMaximum clique problem
Branch-and-bound
Incremental MaxSAT Reasoning
Branching ordering
Issue Date2017
PublisherElsevier
CitationComputers and Operations Research 84: 1- 15 (2017)
AbstractWhen searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy. ©2017 Elsevier Ltd. All rights reserved.
URIhttp://hdl.handle.net/10261/155298
DOIhttp://dx.doi.org/10.1016/j.cor.2017.02.017
Identifiersdoi: 10.1016/j.cor.2017.02.017
issn: 0305-0548
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
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.