• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

A new branch-and-bound algorithm for the maximum edge-weighted clique problem

San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019), A new branch-and-bound algorithm for the maximum edge-weighted clique problem, European Journal of Operational Research, 278, 1, p. 76-90. 10.1016/j.ejor.2019.03.047

Type
Article accepté pour publication ou publié
Date
2019
Journal name
European Journal of Operational Research
Volume
278
Number
1
Publisher
Elsevier
Pages
76-90
Publication identifier
10.1016/j.ejor.2019.03.047
Metadata
Show full item record
Author(s)
San Segundo, Pablo
autre
Coniglio, Stefano
University of Southampton - Mathematical Sciences
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
ESSEC Business School
Abstract (EN)
We study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances.
Subjects / Keywords
Combinatorial optimization; Branch-and-bound; Maximum edge-weighted clique problem

Related items

Showing items related by title and author.

  • Thumbnail
    The maximum clique interdiction problem 
    Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo (2019) Article accepté pour publication ou publié
  • Thumbnail
    An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem 
    Furini, Fabio; Gabrel, Virginie; Ternier, Ian-Christopher (2017) Article accepté pour publication ou publié
  • Thumbnail
    An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
  • Thumbnail
    ILP and CP Formulations for the Lazy Bureaucrat Problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2015) Communication / Conférence
  • Thumbnail
    Benders decomposition for very large scale partial set covering and maximal covering location problems 
    Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo