Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

An Exact Algorithm for the Maximum Weight Clique Problem in Large Graphs

Abstract : We describe an exact branch-and-bound algorithm for the maximum weight clique problem (MWC), called WLMC, that is especially suited for large vertex-weighted graphs. WLMC incorporates two original contributions: a preprocessing to derive an initial vertex ordering and to reduce the size of the graph, and incremental vertex-weight splitting to reduce the number of branches in the search space. Experiments on representative large graphs from real-world applications show that WLMC greatly outperforms relevant exact and heuristic MWC algorithms, and refute the prevailing hypothesis that exact MWC algorithms are less adequate for large graphs than heuristic algorithms.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636428
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:24
Dernière modification le : samedi 6 août 2022 - 03:51:15

Identifiants

  • HAL Id : hal-03636428, version 1

Collections

Citation

Hua Jiang, Chu-Min Li, Felip Manya. An Exact Algorithm for the Maximum Weight Clique Problem in Large Graphs. THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, Feb 2017, San Francisco, United States. pp.830-838. ⟨hal-03636428⟩

Partager

Métriques

Consultations de la notice

28