Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound

DOI10.1016/j.dam.2017.01.026zbMath1462.05338OpenAlexW2593997691MaRDI QIDQ2030442

Satoshi Shimizu, Kazuaki Yamaguchi, Sumio Masuda, Toshiki Saitoh

Publication date: 7 June 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.01.026

zbMATH Keywords

branch-and-boundNP-hardnessexact algorithmmaximum weight cliqueupper bound calculation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ Parallelization of a branch-and-bound algorithm for the maximum weight clique problem ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact bit-parallel algorithm for the maximum clique problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• A fast algorithm for the maximum weight clique problem
• The maximum clique problem
• A fast algorithm for the maximum clique problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Improvements to MCS algorithm for the maximum clique problem
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• On Importance of a Special Sorting in the Maximum-Weight Clique Algorithm Based on Colour Classes
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• Finding a Maximum Clique in an Arbitrary Graph
• A tutorial on branch and cut algorithms for the maximum stable set problem
• A branch and bound algorithm for the maximum clique problem
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• Error-correcting codes over an alphabet of four elements

This page was built for publication: Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound