A new upper bound for the maximum weight clique problem

DOI10.1016/j.ejor.2018.03.020zbMath1403.90640OpenAlexW2790214862WikidataQ130107384 ScholiaQ130107384MaRDI QIDQ1754725

Felip Manyà, Hua Jiang, Yanli Liu, Yu Li, Chu-Min 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

upper boundcombinatorial optimizationbranch and boundmaximum weight clique problemweight cover

Mathematics Subject Classification ID

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

Related Items (10)

Boosting ant colony optimization via solution prediction and machine learning ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ 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 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 ⋮ A Fast Algorithm for Knapsack Problem with Conflict Graph

Uses Software

• MaxCliqueDyn
• 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
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• PUSH: A generalized operator for the maximum vertex weight clique problem
• Optimizing with minimum satisfiability
• 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
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique

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