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

DOI10.1016/J.COR.2019.05.017MaRDI QIDQ2002840zbMATH OpenOpenAlexWikidataFDO

Authors Pablo San Segundo, Fabio Furini, Jorge Artieda

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)

Recommendations

• A new upper bound for the maximum weight clique problem
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• A fast algorithm for the maximum weight clique problem
• A new algorithm for the maximum-weight clique problem
• A maximum edge-weight clique extraction algorithm based on branch-and-bound

Cites work

• scientific article; zbMATH DE number 1947416 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A Primer in Column Generation
• A fast algorithm for the maximum clique problem
• A new exact maximum clique algorithm for large and massive sparse graphs
• A new upper bound for the maximum weight clique problem
• A review on algorithms for maximum clique problems
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• An adaptive multistart tabu search approach to solve the maximum clique problem
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• An exact algorithm for the maximum clique problem
• An exact approach for the vertex coloring problem
• An exact bit-parallel algorithm for the maximum clique problem
• An improved bit parallel exact maximum clique algorithm
• Approximating the maximum vertex/edge weighted clique using local search
• BOB: Improved winner determination in combinatorial auctions and generalizations
• Clique-detection models in computational biochemistry and genomics
• Improved infra-chromatic bound for exact maximum clique search
• Incremental Upper Bound for the Maximum Clique Problem
• Infra-chromatic bound for exact maximum clique search
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Relaxed approximate coloring in exact maximum clique search
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(16)

• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• A maximum edge-weight clique extraction algorithm based on branch-and-bound
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• A New Branch and Bound Algorithm for the Clique Partitioning Problem
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
• Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• A branch-and-cut algorithm for the edge interdiction clique problem
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• A new trust region technique for the maximum weight clique problem
• Boosting ant colony optimization via solution prediction and machine learning
• A new upper bound for the maximum weight clique problem
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• CliSAT: a new exact algorithm for hard maximum clique problems

Describes a project that uses

Uses Software

• DIMACS
• BBMCL
• BBMCSP

This page was built for publication: A new branch-and-bound algorithm for the maximum weighted clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2002840)