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

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

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