Exact algorithms for maximum clique: a computational study

DOI10.3390/a5040545zbMath1461.90162arXiv1207.4616OpenAlexW3103809129MaRDI QIDQ1736530

Patrick Prosser

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4616

zbMATH Keywords

maximum cliqueempirical studyexact algorithms

Mathematics Subject Classification ID

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

Related Items

Parallel Maximum Clique Algorithms with Applications to Network Analysis, A review on algorithms for maximum clique problems, On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, Infra-chromatic bound for exact maximum clique search, A new exact maximum clique algorithm for large and massive sparse graphs, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, On comparing algorithms for the maximum clique problem, The stable set problem: clique and nodal inequalities revisited, Incremental Upper Bound for the Maximum Clique Problem, Why Is Maximum Clique Often Easy in Practice?, Exact algorithms for maximum clique: a computational study, Editorial: Special issue on graph algorithms, Multi-threading a state-of-the-art maximum clique algorithm, An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem, A parallel maximum clique algorithm for large and massive sparse graphs, Relaxed approximate coloring in exact maximum clique search, Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection, Estimating clique size by coloring the nodes of auxiliary graphs, Dynamic node packing, A parallel branch and bound algorithm for the maximum labelled clique problem

Uses Software

• MaxCliqueDyn
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact bit-parallel algorithm for the maximum clique problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• 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
• The maximum clique problem
• A fast algorithm for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• An improved bit parallel exact maximum clique algorithm
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Smallest-last ordering and clustering and graph coloring algorithms
• A Sufficient Condition for Backtrack-Free Search
• Collective dynamics of ‘small-world’ networks
• The Enumeration of Maximal Cliques of Large Graphs
• Algorithm 457: finding all cliques of an undirected graph
• Principles and Practice of Constraint Programming – CP 2003
• A branch and bound algorithm for the maximum clique problem