Exact algorithms for maximum clique: a computational study

DOI10.3390/A5040545MaRDI QIDQ1736530zbMATH OpenOpenAlexFDO

Authors 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://arxiv.org/abs/1207.4616

zbMATH Keywords

maximum cliqueexact algorithmsempirical study

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We investigate a number of recently reported exact algorithms for the maximum clique problem (MCQ, MCR, MCS, BBMC). The program code used is presented and critiqued showing how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The minimum width order (smallest-last) is investigated, and MCS is broken into its consituent parts and we discover that one of these parts degrades performance. It is shown that the standard procedure used for rescaling published results is unsafe.

Recommendations

• An exact algorithm for the maximum clique problem
• An exact algorithm for the maximum quasi‐clique problem
• An exact algorithm for the maximum probabilistic clique problem
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• A new algorithm for the maximum clique problem
• scientific article; zbMATH DE number 2226810
• scientific article; zbMATH DE number 1424217
• A review on algorithms for maximum clique problems
• Algorithm Theory - SWAT 2004

Cites work

• 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 1947416 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• A branch and bound algorithm for the maximum clique problem
• A fast algorithm for the maximum clique problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Algorithm 457: finding all cliques of an undirected graph
• An algorithm for finding a maximum clique in a graph
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An exact bit-parallel algorithm for the maximum clique problem
• An improved bit parallel exact maximum clique algorithm
• An improved branch and bound algorithm for the maximum clique problem
• Collective dynamics of `small-world' networks
• Exact algorithms for maximum clique: a computational study
• Smallest-last ordering and clustering and graph coloring algorithms
• The Enumeration of Maximal Cliques of Large Graphs
• The maximum clique problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Using constraint programming to solve the maximum clique problem

Cited in

(35)

• Relaxed approximate coloring in exact maximum clique search
• Dynamic node packing
• Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
• Estimating clique size by coloring the nodes of auxiliary graphs
• A study of ACO capabilities for solving the maximum clique problem
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Parallel maximum clique algorithms with applications to network analysis
• An exact exponential time algorithm for counting bipartite cliques
• hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
• Computing maximum \(k\)-defective cliques in massive graphs
• A parallel branch and bound algorithm for the maximum labelled clique problem
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• Editorial: Special issue on graph algorithms
• On comparing algorithms for the maximum clique problem
• Speeding up MCS algorithm for the maximum clique problem with ILS heuristic and other enhancements
• A new exact maximum clique algorithm for large and massive sparse graphs
• Infra-chromatic bound for exact maximum clique search
• Multi-threading a state-of-the-art maximum clique algorithm
• An effective branch-and-bound algorithm for the maximum s-bundle problem
• Improvements to MCS algorithm for the maximum clique problem
• An experimental analysis of exact algorithms for the maximum clique problem
• The stable set problem: clique and nodal inequalities revisited
• An Exact Algorithm for the Minimum Dominating Clique Problem
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• Incremental Upper Bound for the Maximum Clique Problem
• Evaluating the effects of the clique selection in exact graph colouring algorithms
• Why is maximum clique often easy in practice?
• A review on algorithms for maximum clique problems
• Worst-case analysis of clique MIPs
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• scientific article; zbMATH DE number 1424217 (Why is no real title available?)
• An algorithm for reporting maximal \(c\)-cliques
• Exact algorithms for maximum clique: a computational study
• A parallel maximum clique algorithm for large and massive sparse graphs

Describes a project that uses

Uses Software

• Algorithm 457
• MaxCliqueDyn

This page was built for publication: Exact algorithms for maximum clique: a computational study

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