Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

Abstract : When 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. (C) 2017 Elsevier Ltd. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636427
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:23
Dernière modification le : lundi 11 avril 2022 - 03:31:05

Identifiants

Collections

Citation

Chu-Min Li, Hua Jiang, Felip Manya. On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. Computers & Operations Research, 2017, 84, pp.1-15. ⟨10.1016/j.cor.2017.02.017⟩. ⟨hal-03636427⟩

Partager

Métriques

Consultations de la notice

23