Multi-threading a state-of-the-art maximum clique algorithm

DOI10.3390/A6040618MaRDI QIDQ1736587zbMATH OpenOpenAlexFDO

Authors Ciaran McCreesh, Patrick Prosser

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a6040618

zbMATH Keywords

maximum cliquemulti-coreparallel algorithmsparallel branch and bound

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parallel algorithms in computer science (68W10)

Review text

Summary: We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.

Recommendations

• A parallel implementation for the maximum clique problem
• scientific article; zbMATH DE number 1424217
• About parallelization of an algorithm for the maximum clique problem
• Parallel maximum clique algorithms with applications to network analysis
• scientific article; zbMATH DE number 4072403
• An improved bit parallel exact maximum clique algorithm
• A parallel maximum clique algorithm for large and massive sparse graphs
• An exact bit-parallel algorithm for the maximum clique problem
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• A fast algorithm for the maximum clique problem

Cites work

• A simple and faster branch-and-bound algorithm for finding a maximum clique
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact bit-parallel algorithm for the maximum clique problem
• An improved bit parallel exact maximum clique algorithm
• Anomalies in parallel branch-and-bound algorithms
• Clique-detection models in computational biochemistry and genomics
• Exact algorithms for maximum clique: a computational study
• Fast algorithms for the maximum clique problem on massive sparse graphs
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 1424217 (Why is no real title available?)
• Improvements to MCS algorithm for the maximum clique problem
• Parallel Branch-and-Branch Algorithms: Survey and Synthesis

Cited in

(12)

• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
• Parallelization of a branch-and-bound algorithm for the maximum weight clique problem
• A parallel branch and bound algorithm for the maximum labelled clique problem
• A review on algorithms for maximum clique problems
• Solving the maximum vertex weight clique problem via binary quadratic programming
• A new exact maximum clique algorithm for large and massive sparse graphs
• Parallel maximum clique algorithms with applications to network analysis
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• About parallelization of an algorithm for the maximum clique problem
• A parallel maximum clique algorithm for large and massive sparse graphs
• A parallel implementation for the maximum clique problem

This page was built for publication: Multi-threading a state-of-the-art maximum clique algorithm

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