Parallelization of a branch-and-bound algorithm for the maximum weight clique problem

DOI10.1016/j.disopt.2021.100646zbMath1506.90264OpenAlexW3162614331MaRDI QIDQ2234743

Satoshi Shimizu, Kazuaki Yamaguchi, Sumio Masuda

Publication date: 19 October 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2021.100646

zbMATH Keywords

branch-and-boundparallel algorithmNP-hardexact algorithmmaximum weight clique

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 (1)

Scatter search with stochastic beam search on the coalition formation problem

Uses Software

• DIMACS
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parllel algorithm for finding a maximum weight clique of an interval graph
• An exact algorithm for the maximum clique problem
• Approximating the maximum vertex/edge weighted clique using local search
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• A review on algorithms for maximum clique problems
• An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem
• On Importance of a Special Sorting in the Maximum-Weight Clique Algorithm Based on Colour Classes
• Reducibility among Combinatorial Problems
• Error-correcting codes over an alphabet of four elements

This page was built for publication: Parallelization of a branch-and-bound algorithm for the maximum weight clique problem