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

DOI10.1016/j.cor.2019.05.017zbMath1458.90624OpenAlexW2945384365WikidataQ127850747 ScholiaQ127850747MaRDI QIDQ2002840

Pablo San Segundo, Jorge Artieda, Fabio Furini

Publication date: 12 July 2019

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2019.05.017

zbMATH Keywords

branch-and-bound algorithmcomputational resultsmaximum weighted clique problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Boosting ant colony optimization via solution prediction and machine learning, CliSAT: a new exact algorithm for hard maximum clique problems, A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, A branch-and-cut algorithm for the edge interdiction clique problem, A new branch-and-filter exact algorithm for binary constraint satisfaction problems

Uses Software

• DIMACS
• BBMCL
• BBMCSP

Cites Work

• Unnamed Item
• Unnamed Item
• Infra-chromatic bound for exact maximum clique search
• A new exact maximum clique algorithm for large and massive sparse graphs
• An adaptive multistart tabu search approach to solve the maximum clique problem
• An exact approach for the vertex coloring problem
• An exact bit-parallel algorithm for the maximum clique problem
• BOB: Improved winner determination in combinatorial auctions and generalizations
• An exact algorithm for the maximum clique problem
• Approximating the maximum vertex/edge weighted clique using local search
• The ellipsoid method and its consequences in combinatorial optimization
• A fast algorithm for the maximum clique problem
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• A new upper bound for the maximum weight clique problem
• An improved bit parallel exact maximum clique algorithm
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Relaxed approximate coloring in exact maximum clique search
• Clique-detection models in computational biochemistry and genomics
• A review on algorithms for maximum clique problems
• An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• A Column Generation Approach for Graph Coloring
• Incremental Upper Bound for the Maximum Clique Problem
• A Primer in Column Generation