A new upper bound for the maximum weight clique problem

DOI10.1016/J.EJOR.2018.03.020MaRDI QIDQ1754725zbMATH OpenOpenAlexWikidataFDO

Authors Chu-Min Li, Yanli Liu, Hua Jiang, Felip Manya, Y. Li

Publication date 31 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2018.03.020

zbMATH Keywords

branch and boundcombinatorial optimizationmaximum weight clique problemupper boundweight cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A new branch-and-bound algorithm for the maximum weighted clique problem
• An exact algorithm based on MaxSAT reasoning 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 maximum edge-weight clique extraction algorithm based on branch-and-bound

Cites work

• A new exact maximum clique algorithm for large and massive sparse graphs
• A review on algorithms for maximum clique problems
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• An improved bit parallel exact maximum clique algorithm
• An improved branch and bound algorithm for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Infra-chromatic bound for exact maximum clique search
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Optimizing with minimum satisfiability
• PUSH: A generalized operator for the maximum vertex weight clique problem
• Relaxed approximate coloring in exact maximum clique search

Cited in

(19)

• Maximum weight relaxed cliques and Russian doll search revisited
• Maximum dispersion and geometric maximum weight cliques
• A new branch-and-bound algorithm for the maximum weighted clique problem
• 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
• Boosting ant colony optimization via solution prediction and machine learning
• The maximum weighted submatrix coverage problem: a CP approach
• A new family of facet defining inequalities for the maximum edge-weighted clique problem
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• A new trust region technique for the maximum weight clique problem
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
• On graphs with polynomially solvable maximum-weight clique problem
• scientific article; zbMATH DE number 7192822 (Why is no real title available?)
• A fast algorithm for knapsack problem with conflict graph
• 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

• MaxCliqueDyn
• BBMCSP
• BBMCL

This page was built for publication: A new upper bound for the maximum weight clique problem

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